2
$\begingroup$

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!

$\endgroup$
3
  • 2
    $\begingroup$ have a look here in this article web.eecs.umich.edu/~cpeikert/pubs/ideal-lwe.pdf $\endgroup$
    – Don Freecs
    May 19 at 18:13
  • 2
    $\begingroup$ for the second question they choose $X^{2^k}+1$ because it useful to use FFT and hence improving efficiency $\endgroup$
    – Don Freecs
    May 19 at 18:16
  • 1
    $\begingroup$ Thanks! It makes perfect sense for the second question, and I'll work on the article for the first question, Thanks again! $\endgroup$
    – fuo55631
    May 19 at 18:36

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks! I think I somewhat get the idea, and I'll work on both articles, Thanks again! $\endgroup$
    – fuo55631
    May 20 at 21:11
  • 2
    $\begingroup$ If this answer fits then please do not forget to accept it! $\endgroup$
    – Maarten Bodewes
    May 24 at 7:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.