Choices of $q$ and $f$ for RLWE-based constructions

Question

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.

Answer 1

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.

Answer 2

While this is an old question, it is perhaps relevant to mention that the CRT can mean more than just leveraging the isomorphism $\mathbb{Z}_q\cong \times_i\mathbb{Z}_{q_i}$. There is a general ring-theoretic result on when one has a ring-isomorphism

$$R / (\cap_i I_i)\cong \times_i R/I_i.$$

This is often still called the Chinese Remainder Theorem. The standard (integer) chinese remainder theorem is recovered by setting $R = \mathbb{Z}$, and $I_i = q_i\mathbb{Z}$. One can also define one over polynomial rings though, for example an isomorphism of the form

$$\mathbb{Z}_q[x]/(x^{2^k}+1) \cong \times_i \mathbb{Z}_q[x]/(x-\omega_q^i) \cong \times_i \mathbb{Z}_q$$

This isomorphism is the isomorphism underlying the NTT, and translates (modular polynomial) multiplication on the LHS to "point-wise" multiplication on the RHS. This is just to say that if someone said that $q \equiv 1\bmod 2n$ is chosen for CRT purposes, it is natural to interpret this as meaning so that the above isomorphism holds, i.e. the isomorphism that enables the NTT to make sense holds.