3
$\begingroup$

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!

$\endgroup$
3
  • 1
    $\begingroup$ I can't speak for quadratic fields, but cyclotomic fields of a power of 2 allows for efficient multiplication of ring elements based on number theoretic transformation (FFT in finite field). Using another field actually can in some way increase our confidence in its security, as is the case with NTRU Prime - they use rings of degree to a prime power. $\endgroup$ – DannyNiu Aug 24 '20 at 10:38
  • $\begingroup$ Chris Peikert is on this site, hope he comes in a drop some words. $\endgroup$ – DannyNiu Aug 24 '20 at 10:39
  • $\begingroup$ I don’t think it’s justified to say that “using another field can in some way increase our confidence in [RLWE’s] security.” The known attacks against RLWE (with appropriate “well spread” error distribution, e.g., following the worst-case hardness theorems) are no better for cyclotomics than for other fields. The same goes for attacks on worst-case poly-approx-SVP on ideal lattices (the worst-case foundation for RLWE with 1/poly error rate). In short, for security of RLWE we currently have no evidence to prefer one type of ring over another. $\endgroup$ – Chris Peikert Aug 24 '20 at 12:59
-3
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ “Multiquadratic fields are not used because there is a quasi-polynomial attack”—no, this is not true for multiple reasons. First, that attack is only against principal ideals that are guaranteed to have an extremely short generator, not worst-case ideals (whether principal or not). Second, that attack isn’t against RLWE itself. $\endgroup$ – Chris Peikert Aug 24 '20 at 12:18
  • 1
    $\begingroup$ Let me add that the quoted text from ePrint 2012/235 overstates the difficulty of using non-two-power cyclotomics. If one simply uses the codifferent ideal $R^\vee$ as recommended in LPR’10, then there is no issue at all with skewed matrices or increasing the magnitude of the errors; see LPR’13. Alternatively, one can avoid using $R^\vee$ using a “tweak” factor and an appropriate error distribution, and lose nothing at all (in security, functionality, or error growth) relative to using $R^\vee$. This is described in Alperin-Sheriff—Peikert CRYPTO’13 and Crockett-Peikert CCS’16, for example. $\endgroup$ – Chris Peikert Aug 24 '20 at 12:49
  • $\begingroup$ Thanks for the clarification! I leave the original text unedited so that viewers can see what is being clarified. I realize RLWE itself is not being attacked, which is why I was intentionally vague about what is being attacked, but I could have been more clear. Often in cryptography we encounter situations where people avoid X not because of an attack against X but because there is a related attack against Y which is not quite equal to X but close enough that people get nervous. (Even if X proper is impervious to the attack, it might be less misuse-resilient than otherwise because of Y.) $\endgroup$ – djao Aug 24 '20 at 13:11
  • 1
    $\begingroup$ Fair enough, but I (along with most experts I’ve talked to) think that the two problems in question are quite far apart. The extremely-short-generator guarantee is essential to the effectiveness of the attack, whether in multiquadratics or cyclotomics. The limitations of the approach for arbitrary ideals are severe, as shown in Cramer—Ducas—Peikert—Regev Eurocrypt’16 and follow-ups. And again, the attack applies to (very special) ideals, not RLWE. $\endgroup$ – Chris Peikert Aug 24 '20 at 13:26
6
$\begingroup$

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).

$\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.