Choosing rings for PLWE

Question

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

Answer 1

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