În primul rând, rețineți că BFV este exprimat în mod tradițional în termeni de aritmetic circuite, nu cele booleene.
De exemplu, lucrarea inițială are un spațiu pentru mesaje din formular $R_t := \mathbb{Z}_t[x] / (\Phi_n(x))$, Unde $\Phi_n$ este $n$al-lea polinom ciclotomic (când $n$ este o putere a doi, aceasta este pur și simplu $x^n+1$).
Acest lucru este relativ important, deoarece blocurile fundamentale ale circuitelor aritmetice sunt nu SAU și ȘI, dar (modul $p$ versiunea) XOR și AND, care este ușor diferită.
În ceea ce privește problemele dvs. cu înmulțirea BFV, cred că citiți ușor specificațiile BFV.
De obicei (să spunem în hârtie inițială) spațiul mesajului este specificat ca fiind $R_t$, care, după cum am menționat anterior, este un inel polinomial (când $n$ este o putere de 2) $\bmod x^n+1$.
Deci, pentru ca schema noastră de criptare să fie complet homomorfă, avem nevoie să putem efectua adunarea și înmulțirea a spațiului de mesaje pe texte cifrate.
Această multiplicare a spațiului mesajului este $\bmod x^n+1$ (și $\bmod t$, dar orice), după cum ați subliniat.
Aceasta înseamnă că ființa aritmetică $\bmod x^n+1$ este ceea ce este necesar din punct de vedere matematic pentru ca schema să fie complet homomorfă, deci produsul fiind de acea formă este de așteptat, și nu o preocupare.
Desigur, designerii de aplicații ar putea să nu dorească să folosească această „aritmetică amuzantă”.
Acesta este un lucru pe care designerii de biblioteci trebuie să îl rezolve mai târziu.
De exemplu, o modalitate de a „remedia” acest lucru (ceea ce este destul de naiv --- bănuiesc că există soluții mai bune) este să codificați mesajele numai în termeni constanti ai polinoamelor.
Ar trebui să fie relativ simplu să vedem că această „înmulțire amuzantă” devine o înmulțire standard atunci când este limitată la polinoame constante.
Există și alte lucruri pe care le-ar putea face, de exemplu, s-ar putea permite polinoame de formă $m(x) = m_0+m_1x$ dacă știți că adâncimea multiplicativă a circuitului pe care îl evaluați este de cel mult $\log_2 n$, sau mai general $m(x) = \sum_{i =0}^p m_i x^i$ dacă adâncimea multiplicativă este de cel mult $\log_{1+p} n$.
Acest lucru se datorează faptului că, cu această limită de adâncime, nu se poate produce un polinom de grad $\geq n$, deci faptul că înmulțirea s-ar putea „încheia” nu contează.
Desigur, sunt sigur că există idei mai inteligente despre ce se poate face pentru a emula aritmetica „standard” cu aritmetica „amuzant” pe care o obține, dar asta este într-adevăr ortogonal la înțelegerea BFV.
este de asemenea merită menționat că comentariul tău
dar trebuie să fie în funcție de coeficienți și pe polinom, nu și pentru polinoamele în sine
se pare că s-ar putea să cauți ideea încorporare canonică.
Mai exact, s-a observat în urmă cu aproximativ un deceniu că dacă vrem un tip de date asemănător matricei $[a_0,\dots,a_n]$ pe care se poate efectua aritmetică (în funcție de slot), atunci coeficienții polinoamelor sunt într-adevăr o alegere destul de proastă.
Aceasta deoarece (printre altele) operația naturală de înmulțire pe polinoame nu duce la înmulțirea coeficienților de bază, ci convoluţie dintre ei.
În special, unul are asta
$$(a_0+a_1x+a_2x^2)(b_0+b_1x+b_2x^2) = a_0b_0+(a_0b_1+b_0a_1)x + (a_0b_2+a_1b_1+a_2b_0)x^2+(a_1b_2+a_2+a_1b_2+a_2_2_2) ^4$$
În special, nu se recuperează produsul $a_1b_1$.
Se poate rezolva acest lucru făcând (în esență) apel la o versiune a transformării Fourier, deoarece o transformată Fourier poate fi scrisă de obicei ca un izomorfism.
$$\mathcal{F} : (R, +,\times)\la (R, +,\ast)$$
de exemplu. se „schimbă” convoluția cu înmulțirea (în funcție de coeficienți).
Aceasta înseamnă că, dacă în schimb codificăm un mesaj în „încorporarea canonică” (sau echivalent, codificăm „transformarea Fourier” a mesajului), atunci convoluțiile vor deveni o multiplicare în funcție de elemente (în spațiul nostru de mesaje).
Nu cred că lucrarea inițială BFV face acest lucru, ceea ce, în funcție de ceea ce citiți pentru o specificație a BFV, poate duce la confuzie.
Dar cred că este o optimizare relativ comună și ar trebui să poată fi văzută ca „doar” o codificare diferită a mesajelor (există și alte beneficii în utilizarea încorporarii canonice, astfel încât să doriți să reanalizați protocolul în termeni).
