RLWE Explicație

În RLWE, alegem adesea următorul inel polinom, unde q este prim, iar n este o putere de 2, de ex. $2^k$ $$\mathbb Z_q[X]/(X^n + 1)$$

Noi stim aia ${X^{2^k}} + 1$ este un polinom ireductibil sub $Z$, din cauza Polinom ciclotomic, dar în acest întrebare, Luand in considerare $$\mathbb Z_{17}[X]/(X^4 + 1)$$ $(X^4 + 1)$ poate fi factorizat în $$\mathbb (X^2 + 4)(X^2 - 4) = X^4 - 16 = X^4 + 1$$ din cauza $Z_{17}$, în plus, poate fi chiar factorizat în $(x + 15)(x + 9)(x + 8)(x + 2)$ sub $Z_{17}$

Atunci de ce ar trebui să alegem un polinom ireductibil ca ${X^{2^k}} + 1$ în primul rând când este reductibilă sub $Z_q$, mai mult, care sunt avantajele alegerii ${X^{2^k}} + 1$ ca al nostru ideal, și alegerea unui q prim suficient de mare (mult mai mare decât 17) împiedică scenariul de mai sus să se întâmple?

Mulțumiri!

Polinoamele ciclotomice sunt utilizate în dovezile că problemele de rețea din cel mai rău caz se reduc la RLWE. Dacă încercați să instanțiați RLWE cu alte polinoame, atunci nu aveți astfel de garanții formale cu privire la duritatea problemei. Poti sa verifici acest set de diapozitive de Peikert pentru o introducere, apoi citiți referințele dacă doriți mai multe detalii.

Și alegerea $q$ astfel încât polinomul ciclotomic să nu se divizeze complet este inutil, deoarece duritatea problemei RLWE depinde doar de lungimea biților a $q$, nu pe formatul său.

Apropo, atunci când implementăm BGV, FV, CKKS sau alte scheme bazate pe RLWE, deseori ne limităm opțiunile de $q$ a forta $X^n + 1$ să se împartă complet, ca să putem folosi Reprezentare RNS (aka double-CRT)..