Study group: Provably weak instances of Ring-LWE

After Ryan's study group last week, it was my turn this morning to present my chosen paper, Provably Weak Instances of Ring-LWE.

The authors build up on previous attack on Poly-LWE (EHL) to extend the attack to a larger class of number fields, and show how to apply that to construct an attack on Ring-LWE.

In a nutshell, Ring-LWE instances can be mapped into Poly-LWE ones, and if the distortion is not too large and there is an attack on the Poly-LWE instance, then this can be mapped back. The distortion is governed by the spectral norm of the mapping, which we define later on.

Let us begin by re-stating the Poly-LWE problem. From now on, we take $f(x)$ to be a monic irreducible polynomial in $\mathbb{Z}[x]$ of degree $n$ and $q$ to be a prime such that $f$ factors completely modulo $q$ and has no repeated roots. Let $P = \mathbb{Z}[x]/(f(x))$ and $P_q = P/qP = \mathbb{F}_q[x]/(f(x))$. We denote the uniform distribution by $\mathcal{U}$ and the discrete spherical (with respect to power basis) Gaussian of mean 0 and variance $\sigma^2$ by $\mathcal{G}_\sigma$, both on $P_q$.

Decision Poly-LWE Problem: Let $s(x) \in P_q$ be a secret, drawn from the uniform distribution. The Decision Poly-LWE problem is to distinguish, with non-negligible advantage, between the same number of independent samples in two distributions of $P_q \times P_q$. The first consists of samples of the form $(a(x), b(x)=a(x)s(x)+e(x))$, where $e(x)$ has been drawn from $\mathcal{G}_{\sigma}$ and $a(x)$ from the uniform distribution. The second consists of uniformly random and independent samples from $P_q \times P_q$.

It is worth mentioning that this is slightly non-standard terminology. PLWE differs from RLWE in that RLWE samples the errors in the Minkowski embedding and then pulls these values back to obtain polynomials, whereas PLWE samples the polynomial coefficients directly. Now that we have established the problem, let's break it.

The attack on Poly-LWE is fairly straightforward. It proceeds as such.

1. Map the problem down to $\mathbb{F}_q$ via a homomorphism $\phi$.
2. Loop through all possible guesses of the image of the secret $\phi(s(x))$.
3. Gather the values $\phi(e_i(x))$ under the assumption that the guess is correct.
4. Examine the resulting samples to try and determine whether they are images of a uniform distribution or a Gaussian one.

We recall that in a previous work, an attack was presented in the case when $f$ has a root $\alpha \equiv 1 (\mod q)$ or has a root of small order modulo $q$.

We first map everything down to $\mathbb{F}_q$. Write $f(x) = \prod_{i=o}^{n-1} (x - \alpha_i)$, which we can do by assumption. We then use the Chinese Remainder Theorem to write

$P_q \cong \prod_{i=o}^{n-1}\mathbb{F}_q[x]/(x-\alpha_i) \cong \mathbb{F}^n_q$.

For each root $\alpha_i$ of $f$ (of which we recall there are $n$), there is a ring homomorphism

$\phi : P_q \rightarrow \mathbb{F}_q[x]/(x-\alpha_i) \cong \mathbb{F}_q$,

obtained by simply evaluating $g(x) \in P_q$ at the said root. We fix a root $\alpha = \alpha_i$. We then loop through all $g \in \mathbb{F}_q$, where each $g$ is taken as a guess for the image of the secret $s(\alpha)$. Assuming this is correct, we obtain

$e_i(\alpha) = b_i(\alpha) - a_i(\alpha)g = b_i(\alpha) - a_i(\alpha)s(\alpha)$.

If our samples were of LWE nature, then the collection of ${e_i(\alpha)}_i$ will be distributed as the original errors. Thus this method relies on $\phi(\mathcal{U})$ and $\phi(\mathcal{G}_\sigma$ being distinguishable, as well as $q$ being small enough to allow looping through $\mathbb{F}_q$. We present the first algorithm in the paper; the other, based on the size of the error values, is similar and can be found here. It runs as follows.

We assume that $f$ has a root $\alpha$ of small order $r$ modulo $q$, i.e. $\alpha^r \equiv 1 \mod q$. Then

 $e(\alpha) = \sum e_i\alpha^i = (e_0 + e_r + e_2r + ...) + \alpha(e_1 + e_r+1 +...) + \alpha^r-1(e_r-1 + ...)$.

If $r$ is small enough, then the above sum only takes on a small number of values modulo $q$; which  allow us to efficiently distinguish whether a given value modulo $q$ belongs to that set of values. So let $S$ be the set of possible values of $e(\alpha)$ modulo $q$, notice it has size $(4\sigma n/r)^r$.

• Let $G$ be an empty list
• For $g \in \mathbb{F}_q$ from 0 to $q-1$, for (a(x), b(x)) in the collection
• if $b(\alpha)-ga(\alpha)$ does not equal an element of $S$ then break
• otherwise append $g$ to $G$

• If $G$ is empty, return NOT PLWE
• If $G = {g}$, return $g$
• If $|G| > 1$ return INSUFFICIENT SAMPLES

To finish this blog post, we explain how the authors move the attack from Poly-LWE to Ring-LWE. Suppose $K$ is a monogenic number field and $R$ its ring of integers, so that $R$ is isomorphic to the polynomial ring $P = \mathbb{Z}[x]/(f(x))$ for some monic irreducible $f$. Let $\Phi(R)$ be its canonical embedding into $\mathbb{R}^n$. Then there is a map which we'll denote by $M_\alpha$ giving an isomorphism $M_\alpha : P \rightarrow \Phi(R)$. We define the spectral norm of this map as the radius of the smallest ball containing the image of the unit ball under $M_\alpha$. This will govern the distortion of the error distribution on $\Phi(R)$. And if it not too large, then a solution to the Poly-LWE problem with the new spherical Gaussian distribution may be possible. In which case, it will give a solution to the original Ring-LWE problem. Loosely speaking, we require that the following conditions are satisfied.

1. $K$ is monogenic.
2. $f$ satisfies $f(1) \equiv 0 \mod q$ (or has a root of small order, as seen).
3. $\rho$ and $\sigma$ are sufficiently small.

If we denote the spectral norm by $\rho$, the main theorem in the paper tells us that if the spectral norm satisfies

$\rho < q/(4 \sqrt{2\pi}\sigma n)$,

then the (non-dual) Ring-LWE problem decision problem can be solved (for parameters) in time $\widetilde{O}(lq)$ with probability $1-2^{-l}$, where we recall $l$ is the number of samples.