RLWE Explanation

Question

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?

Thanks!

Answer 1

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.