Can someone please tell me why in R-LWE we always make use of Cyclotomic fields, and specially those with degree equals to a power of $2$?
Can we use another fields without losing in hardness of the problem?
What about Quadratic fields for example?
Thank you!
Power of 2 is explained in ePrint 2012/235:
the results from [LPR10] do not directly imply that the above problem is hard based on the worstcase hardness of lattice problems, except in the one case when $f(X) = X^n+1$ for $n$ a power of $2$, and thus most papers that use the Ring-LWE problem only use this one specific ring. The reason for this limitation is that the problem statement in [LPR10] requires $w$ to be in the dual ring of $R$ (which is a fractional ideal) and for the distribution of the noise to be a spherical Gaussian in the embedding representation of $R$. And it is only in the case that $R = \mathbb{Z}[X]/(X^n + 1)$ that the dual ring is simply a scaling of $R$ (thus, one can simply multiply by the scaling and end up in $R$) and the embedding is just a rigid rotation and a scaling (thus the spherical Gaussian distribution is not affected by the transformation). For all other cyclotomic polynomials, while it is possible to transform the problem that was proved hard in [LPR10] to the one described above, the transformation between the polynomial and embedding representations involves multiplication by a skewed matrix, and the dual of $R$ is a (possibly very) skewed fractional ideal of $R$. Therefore there is no obvious way to generate the noise directly in the ring $R$, nor work entirely in the ring $R$ without utilizing a transformation that can substantially increase the magnitude of the error polynomials.
Multiquadratic (and hence quadratic) fields are not used because there is a quasi-polynomial attack, which is much too long to describe here. For details see this 55-page paper.
We don’t always use power-of-two cyclotomics for RLWE. Many cryptosystems use other cyclotomics, or subfields thereof, or even other fields altogether. For example, many FHE schemes use non-two-power cyclotomics for “packing” and SIMD operations on plaintexts.
However, it is simplest to properly define and use RLWE over two-power cyclotomics, in large part because one can easily avoid using the “codifferent” (fractional) ideal $R^\vee$. (Other associated operations, like the NTT/CRT algorithm, are simpler in the two-power case as well.) So, this is probably why people tend to stick with two-power cyclotomics for RLWE.
The use of fields other than two-power cyclotomics can be justified by theory. The original LPR’10 paper proved the hardness of search-RLWE over any number field (not just cyclotomics), based on the conjectured quantum hardness of worst-case approximate-SVP on ideal lattices in that same number field. It also proved the hardness of decision-RLWE, assuming the hardness of search, for any cyclotomic number field (whether two-power or not); it turns out that this proof also works just as well for arbitrary Galois number fields, e.g., multiquadratics. Later, Peikert—Regev—Stephens-Davidowitz’17 directly proved the hardness of decision-RLWE over any number field (whether Galois or not), based on the same assumption as in the first sentence of this paragraph.
As for whether we can use quadratic fields, all of the above applies equally well for them, but the dimension is so small that worst-case SVP is easy—even on arbitrary lattices, not just ideal lattices. Similarly, RLWE over a quadratic field is trivially easy (except possibly if one used an enormous modulus, but this is not typical).
