RLWE Explanation

cn flag

In RLWE, we often choose the following polynomial ring, where q is a prime, and n is a power of 2, e.g. $2^k$ $$\mathbb Z_q[X]/(X^n + 1)$$

We know that ${X^{2^k}} + 1$ is an irreducible polynomial under $Z$, because of Cyclotomic Polynomial, but in this question, Considering $$\mathbb Z_{17}[X]/(X^4 + 1)$$ $(X^4 + 1)$ can be factorized into $$\mathbb (X^2 + 4)(X^2 - 4) = X^4 - 16 = X^4 + 1$$ because of $Z_{17}$, moreover it can even be factorized into $(x + 15)(x + 9)(x + 8)(x + 2)$ under $Z_{17}$

Then why would we need to choose an irreducible polynomial like ${X^{2^k}} + 1$ at the first place when it is reducible under $Z_q$, moreover what are the advantages of choosing ${X^{2^k}} + 1$ as our ideal, and does choosing a large enough prime q(much larger than 17) prevents the above scenario from happening?


Don Freecs avatar
sz flag
have a look here in this article
Don Freecs avatar
sz flag
for the second question they choose $X^{2^k}+1$ because it useful to use FFT and hence improving efficiency
cn flag
Thanks! It makes perfect sense for the second question, and I'll work on the article for the first question, Thanks again!
us flag

The cyclotomic polynomials are used in the proofs that worst-case lattice problems reduce to the RLWE. If you try to instantiate RLWE with other polynomials, then you don't have such formal guarantees about the hardness of the problem. You can check this set of slides by Peikert for an introduction, then read the references if you want more details.

And choosing $q$ such that the cyclotomic polynomial does not split completely is useless, because the hardness of the RLWE problem only depends on the bit length of $q$, not on its format.

By the way, when we implement BGV, FV, CKKS or other schemes based on the RLWE, we often restrict our choices of $q$ to force $X^n + 1$ to split completely, so that we can use RNS (aka double-CRT) representation.

cn flag
Thanks! I think I somewhat get the idea, and I'll work on both articles, Thanks again!
Maarten Bodewes avatar
in flag
If this answer fits then please do not forget to accept it!
Hilder Vitor Lima Pereira avatar
us flag
@fuo55631 Please, if there is something missing in the answer, tell me. It is important for the statistics of the site, that answered questions are marked as answered.
I sit in a Tesla and translated this thread with Ai:


Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.