Ring-LWE

Plain Learning With Errors puts the secret in $\mathbb{Z}_q^n$, an ordinary vector with no structure connecting its components. Ring-LWE puts it in $R_q$ instead, so the secret is a polynomial and the components are its coefficients.

That sounds like a change of notation. It is a change of substance, and this note shows exactly what is bought.

01.The definition

Fix the ring $R_q = \mathbb{Z}_q[X]/(X^n + 1)$ from Chapter 1, and an error distribution $\chi$ producing polynomials with small coefficients.

A Ring-LWE sample for a secret $s \in R_q$ is a pair

$$(a,\; b = a \cdot s + e) \;\in\; R_q \times R_q,$$

where $a$ is drawn uniformly from $R_q$, the error $e$ is drawn from $\chi$, and $a \cdot s$ is multiplication in $R_q$.

Compare that with the plain LWE sample from Chapter 3. There, $a$ was a vector, $s$ was a vector, the product was an inner product, and the result $b$ was a single number in $\mathbb{Z}_q$. Here everything is a polynomial and $b$ is a whole polynomial too.

That last difference is the whole point. A plain sample yields one equation. A ring sample yields $n$ of them.

One ring sample carries $n$ plain samples

Work it out on the running parameters $q = 17$, $n = 4$.

Let the secret be $s(X) = 1 + 2X + 3X^2 + 4X^3$, so $s = (s_0, s_1, s_2, s_3) = (1,2,3,4)$. Draw the uniform element $a(X) = 5 + 6X + 7X^2 + 8X^3$ and a small error $e(X) = X - X^2$, so $e = (0, 1, -1, 0)$.

Multiply $a$ by $s$ in $R_{17}$, reducing with $X^4 = -1$ as in Chapter 1. Doing it symbolically, in the unknowns $s_0$ through $s_3$, the four coefficients of the product come out as

$$\begin{aligned} (as)_0 &= 5 s_0 - 8 s_1 - 7 s_2 - 6 s_3, \\ (as)_1 &= 6 s_0 + 5 s_1 - 8 s_2 - 7 s_3, \\ (as)_2 &= 7 s_0 + 6 s_1 + 5 s_2 - 8 s_3, \\ (as)_3 &= 8 s_0 + 7 s_1 + 6 s_2 + 5 s_3 . \end{aligned}$$

Substituting the actual secret $(1,2,3,4)$ and reducing modulo $17$ gives $as = (12, 15, 2, 9)$, and adding the error gives

$$b \;=\; (12,\; 16,\; 1,\; 9) .$$

Now read those four displayed lines as what they are. Each is a linear equation in the four unknown coefficients of the secret, and each has had a small error added. Four plain-LWE equations, produced from a single pair $(a, b)$ of ring elements.

That is the compression, stated precisely. To publish four plain-LWE equations you would have to write down four independent vectors $a_1, \ldots, a_4$, sixteen numbers in total. To publish the same four equations here you write down one polynomial $a$, which is four numbers.

03.Where the missing numbers went

The sixteen numbers did not vanish. They became implicit.

Collect the coefficients of those four equations into a matrix:

$$\operatorname{circ}_-(a) \;=\; \begin{pmatrix} 5 & -8 & -7 & -6 \\ 6 & 5 & -8 & -7 \\ 7 & 6 & 5 & -8 \\ 8 & 7 & 6 & 5 \end{pmatrix} .$$

Look at how it is built. Read down the first column: $5, 6, 7, 8$, which is $a$ itself. Each subsequent column is the previous one shifted down by one position, with the entry that falls off the bottom reappearing at the top with its sign flipped.

That sign flip is $X^4 = -1$, showing up as a structural property of the matrix. A matrix built this way is called a negacyclic circulant.

So multiplying by $a$ in $R_q$ is the same as multiplying by this $n \times n$ matrix. The matrix has $n^2$ entries and every one of them is determined by the $n$ coefficients of $a$. Storing $a$ stores the matrix.

This is where the factor-of-$n$ key compression from Chapter 3 comes from, and now it is visible rather than asserted.

04.What it costs

Nothing is free, and the price here is an assumption.

In plain LWE the matrix $A$ is fully random, all $n^2$ entries independent. In Ring-LWE it is a negacyclic circulant, so $n^2 - n$ of its entries are forced by the other $n$. An attacker therefore knows a great deal about the matrix before seeing it, and can look for attacks that exploit that structure.

Ring-LWE is consequently a stronger assumption than plain LWE. Believing it means believing not only that lattice problems are hard, but that they remain hard on this restricted family of structured lattices.

That worry is not theoretical. Attacks exploiting ring structure have been found for some choices of the modulus polynomial, which is a large part of why $X^n + 1$ with $n$ a power of two is the choice that survived the competition. It is the best-studied case and the one with the fewest exploitable features.

The next note describes the compromise the standards actually adopted, which keeps most of the compression while giving back some of the structure.