1
$\begingroup$

I understand that RLWE was introduced to avoid the quadratic overhead in the matrices that appear in plain LWE. However, I have a series of questions about this setting. First, Ring-LWE-based constructions consider the polynomial ring $R_q = \mathbb{Z}_q[x]/(f(x))$, for some polynomial $f$ and some integer $q$. I've seen the choice $f(x) =x^{2^m} + 1$ and $q$ a prime such that $q\equiv 1\bmod 2^{m+1}$.

Why is this choice of parameters relevant?

I understand that arithmetic in this ring is cheaper because of NTT, but, how does the CRT fit into the picture? Does it help the fact that the ring splits completely?

Also, I have a vague memory of some text that said that CRT is useful because instead of working with large modulus one can work with multiple smaller modulus. I also heard that CRT is useful since you can do "parallel" computations.

How does CRT fit into the RLWE picture?

Finally,

Why does $q$ need to be prime?

Are there some works that consider a composite $q$?

Thanks! Any pointers or comments are more than welcome.

$\endgroup$
2
$\begingroup$

Why use $f(x) = x^{2^n} + 1$?

This is a very special polynomial called a "cyclotomic" polynomial. Cyclotomic polynomials are very interesting, and I recommend reading up on them separately (wikipedia). One very useful property is that the $m^{th}$ cyclotomic polynomial has roots that are all the $m^{th}$ primitive roots of unity. For any $n \geq 1$, the polynomial $f(x) = x^{2^n} + 1$ is the $(2^{n+1})^{th}$ cyclotomic. Power-of-two cyclotomics are even more convenient because they allow for much faster NTT algorithms (see Cooley-Turkey style optimizations, where having a power-of-two length is important for the recursive structure of the algorithm). Here is a nice paper on NTT optimizations.

Where does CRT come in?

This will also answer your third question, since $q$ need not be prime, and this is necessary to implement CRT optimizations. The problem that arises with RLWE-based secure computations is that the modulus $q$ must grow to be much larger than the typical machine word, which is usually 64 bits. Since $q$ need not be prime, we can use a modulus $q$ that is the product of many small primes $q = \prod_{i=0}^{\ell-1} q_i$. CRT makes use of the following isomorphism: $$ \mathbb{Z}_q \cong \mathbb{Z}_{q_0} \otimes \mathbb{Z}_{q_1} \otimes \ldots \otimes \mathbb{Z}_{q_{\ell-1}} $$ This is what allows the implementations to work with each $q_i$ separately instead of the full $q$. This also allows for parallelization. For more information on this isomorphism and how it's useful in RLWE implementation, I recommend this paper.

$\endgroup$

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.