Tightness of the error bound in Ring-LWE

About two months ago we have posted a short paper on eprint sharing some thoughts on the error size used in Ring-LWE, an increasingly important hard problem that was proposed by Lyubashevsky, Peikert and Regev [LPR] as a building block for cryptography. Besides resistance against quantum computers, one of the main features of Ring-LWE for HEAT is that it enables homomorphic encryption.

Very briefly, in Ring-LWE one fixes a degree $n$ number field $K$ with ring of integers $R$ and discriminant $\Delta$. One also fixes an integer modulus $q$ and an error parameter $r \in \mathbb{R}_{> 0}$, which we think of as depending on $n$ only. We write $R_q$ and $R_q^\vee$ for the reduction of $R$ and its codifferent (or `dual') modulo $q$. The Ring-LWE problem is about guessing a secret $\mathbf{s} \in R_q^\vee$ from a number of samples of the form $(\mathbf{a}, \mathbf{a} \cdot \mathbf{s} + \mathbf{e} )$, where $\mathbf{a} \in R_q$ is random and $\mathbf{e}$ is sampled from the distribution on $(K \otimes \mathbb{R})/q\mathbb{Z}$ that one obtains by pulling back a spherical Gaussian of width $r$ under the canonical embedding $K \hookrightarrow \mathbb{R}^n$.

In a recent series of papers Elias, Lauter, Ozman and Stange [ELOS], and Chen, Lauter and Stange [CLS1], [CLS2] investigated whether the existence of a homomorphism $\phi : R_q \rightarrow S$ to some small ring $S$ can be exploited to leak information about the secret $\mathbf{s}$. For instance if $R_q$ is of the form $\mathbb{Z}[x]/(q,f(x))$ for some $f(x) \in \mathbb{Z}[x]$ satisfying $f(1) = 0$ mod $q$, then $\phi$ could be evaluation at $1$: $$\phi : R_q \rightarrow \mathbb{F}_q: \mathbf{a} \mapsto \mathbf{a}(1).$$ Although this idea is attractive, the concrete vulnerable instances proposed by [ELOS], [CLS1], [CLS2] do not follow the original set-up from [LPR]. Instead they

1. sample the secrets from the ring $R_q$, rather than its dual $R_q^\vee$,
2. use an error parameter of the form $|\Delta|^{1/2n}\cdot r$, rather than just $r$.

It is not entirely clear to us what the implications of 1. are, but at least one should scale up the error parameter in order to compensate for the relative sparseness of $R$, as is indeed done in 2. However the scalar $|\Delta|^{1/2n}$ is chosen from a Polynomial-LWE point of view and is not adapted to the way the Ring-LWE errors are generated. Indeed, the canonical embedding may be very skew, so even though `on average' things will be okay, there could exist a basis of $R$ with respect to which some of the coordinates of $\mathbf{e}$ are negligible. This in turn leads to exact linear equations in the secret $\mathbf{s}$, obtained by merely rounding, which allows for a recovery of the secret using elementary linear algebra.

In a previous paper (reported upon in a blogpost below) we showed that the families from [ELOS] indeed suffer from this skewness, and therefore were easy to start from. To some extent this also seems to apply to the examples from [CLS1] and [CLS2], as is discussed in the last section of our current paper, where we make a more systematic analysis of the skewness phenomenon. Our main contributions are as follows:

• We first give an informal motivation for why the most natural choice of scalar is $|\Delta|^{1/n}$, rather than $|\Delta|^{1/2n}$, if one wants to set up a non-dual version of Ring-LWE as in 1.
• Next we provide for any $\varepsilon > 0$ a family of number fields in which non-dual Ring-LWE can again be broken using elementary linear algebra as soon as the errors are scaled up by $|\Delta|^{(1 - \varepsilon)/n}$ only.
• Finally we show that also the actual (i.e., dual) Ring-LWE problem is easily broken for the same families, as soon as the errors proposed by [LPR] as scaled down by $|\Delta|^{\varepsilon/n}$.

So our conclusions strongly suggest that the problems with the examples from [ELOS] are related to 2., rather than 1. They also provide a tightness statement on the error size proposed by [LPR], at least from a discriminant point of view. Immediate research questions that arise are whether there exist weak instances of non-dual Ring-LWE, when set up with the scalar $|\Delta|^{1/n}$, and, more specifically, whether there exist attacks involving a homomorphism $\phi : R_q \rightarrow S$ that apply here? Or that apply to the actual Ring-LWE problem as introduced in [LPR]?

About a month ago Peikert posted a paper sharing similar (but more detailed) thoughts on the vulnerability of the Ring-LWE instantiations described in [ELOS], [CLS1] and [CLS2].

Wouter Castryck, Ilia Iliashenko, Frederik Vercauteren