2
$\begingroup$

In [ELOS15], the authors give an attack on RLWE, and claim that "the hardness of Ring-LWE is... dependent on special properties of the number field" chosen; whereas, responding to prior attacks on RLWE (including the one cited above), in [P16] the author claims that 'the rings themselves are not the source of insecurity in the vulnerable instantiations.' Which is the case? Are certain rings (uniquely?) vulnerable to certain attacks, or is it merely the parameters chosen which make a construction insecure (e.g. a poorly chosen error distribution)?

$\endgroup$
1
$\begingroup$

Section 4 of [P16] is perhaps the key section to read. I quote it below:

We stress that all these insecure instantiations—excepting [EHL14], for which the following conclusions still apply—are for the “non-dual” version of Ring-LWE with spherical Gaussian errors relative to $R$ (in the canonical embedding). By contrast, the definition of Ring-LWE from [LPR10], and the instantiations having worst-case hardness, involve spherical errors relative to the dual ideal $R^\vee$ (see Section 2.3.2). When the insecure and hard instantiations are transformed to be directly comparable, the resulting error distributions turn out to have very different widths and shapes. We return to this point in Section 5, where we show that the hard instantiations are immune to the attacks from Section 3

In fact, this can be understood to be the key difference between Ring-LWE and Poly-LWE --- whether LWE samples:

$$(a(x), a(x)s(x) + e(x))\in\begin{cases}R_q\times R_q^\vee & \text{RLWE}\\ R_q\times R_q & \text{PolyLWE}\end{cases}$$

Note that these are almost equivalent. In particular, at the end of section 2 of [P16] there is a heading called Equivalence of dual and non-dual forms where it is shown that they are equivalent up to the resulting choice of error distribution. And for power-of-two cyclotomics, it is known that this change is multiplication by a small constant, i.e. by a transformation that simply scales the covariance matrix of the underlying error distribution. In general the distributions are related by a certain linear transformation, but it need not be this simple.

[P16] points out that this means that the attacks on weak instances of PolyLWE are implicitly attacks on RLWE, and that the attacks are induced by not accounting for the aforementioned change in the underlying error distribution (which does vary depending on the underlying choice of ring). This means on the RLWE side of things, the error was too small, so the worst-case to average-case reduction was not valid (and therefore the PolyLWE attacks do not imply IdealSVP algorithms, as you might have otherwise expected).

$\endgroup$
1
  • 1
    $\begingroup$ All this is true and useful to address the question, but there is another, simpler, way to see what’s wrong with these weak PLWE parameters without having to get into “dual” RLWE and all the rest. Specifically, the attacked error distributions for the PLWE problems are not “well spread” relative to the polynomial ring $R$. For example, some coefficients of the error polynomials are so small that they lie in (-1/2,1/2) with high probability, and hence round to zero. This is essentially “LWE with no error,” and is trivially insecure. (Feel free use this in your answer if you wish.) $\endgroup$ – Chris Peikert May 19 at 20:46

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.