The Learning With Errors Problem

The previous note demonstrated the effect. This note states the problem formally, gives its two forms, works a full instance, and explains the theorem that makes it worth building a standard on.

01.The definition

Fix a dimension $n$, a modulus $q$, and an error distribution $\chi$ over the integers, concentrated near zero. Let the secret $s \in \mathbb{Z}_q^n$ be drawn uniformly at random.

An LWE sample for the secret $s$ is a pair $(a, b) \in \mathbb{Z}_q^n \times \mathbb{Z}_q$ where

$$a \leftarrow \mathbb{Z}_q^n \text{ uniformly}, \qquad e \leftarrow \chi, \qquad b = \langle a, s \rangle + e \bmod q .$$

The arrow notation $\leftarrow$ means "is drawn at random from". Each sample uses a fresh $a$ and a fresh $e$, but always the same secret $s$.

Two questions can be asked about a pile of such samples, and they have different names.

Search-LWE. Given many samples $(a_1, b_1), (a_2, b_2), \ldots$ for the same unknown $s$, recover $s$.

Decision-LWE. Given many pairs, decide whether they are LWE samples for some hidden $s$, or whether each $b_i$ was simply drawn uniformly at random from $\mathbb{Z}_q$.

Search is the obvious formulation. Decision is the one cryptography actually needs, and the reason is worth spelling out.

An encryption scheme is considered secure when a ciphertext is indistinguishable from random noise. Not merely hard to decrypt, but impossible to tell apart from meaningless bytes. If Decision-LWE is hard, then an attacker holding an LWE-based ciphertext cannot even tell it is a ciphertext, let alone read it. That is a much stronger guarantee than "cannot recover the message", and it is the standard modern definitions demand.

The two forms are equivalent. Given an algorithm for one, you can build an algorithm for the other in polynomial time. So the hardness assumption can be stated in whichever form is convenient.

A full instance over $\mathbb{Z}_{17}$

Take $n = 3$, $q = 17$, and let $\chi$ be uniform on $\{-1, 0, +1\}$. The secret is

$$s \;=\; (5,\, 11,\, 2) \in \mathbb{Z}_{17}^3 .$$

Sample 1. Draw $a_1 = (1, 4, 3)$.

$$\langle a_1, s \rangle \;=\; 1 \cdot 5 + 4 \cdot 11 + 3 \cdot 2 \;=\; 5 + 44 + 6 \;=\; 55 .$$

Reduce: $55 = 3 \cdot 17 + 4$, so $\langle a_1, s \rangle \equiv 4$. Draw $e_1 = +1$. Then $b_1 = 4 + 1 = 5$.

Sample 2. Draw $a_2 = (2, 0, 7)$.

$$\langle a_2, s \rangle \;=\; 10 + 0 + 14 \;=\; 24 \;\equiv\; 7 \pmod{17} .$$

Draw $e_2 = 0$. Then $b_2 = 7$.

Sample 3. Draw $a_3 = (6, 9, 12)$.

$$\langle a_3, s \rangle \;=\; 30 + 99 + 24 \;=\; 153 \;\equiv\; 0 \pmod{17},$$

since $153 = 9 \cdot 17$. Draw $e_3 = -1$, which is $16$ modulo $17$. Then $b_3 = 16$.

The attacker is handed

$$A = \begin{pmatrix} 1 & 4 & 3 \\ 2 & 0 & 7 \\ 6 & 9 & 12 \end{pmatrix}, \qquad b = \begin{pmatrix} 5 \\ 7 \\ 16 \end{pmatrix},$$

and nothing else. As Noise Breaks Linear Algebra showed, inverting gives $(13, 14, 7)$, which is wrong in every component.

03.Being honest about this example

The instance above is not secure and it is important to say so.

With $q = 17$ and $n = 3$ there are only $17^3 = 4913$ possible secrets. An attacker simply tries all of them, checking for each candidate whether every $b_i - \langle a_i, s \rangle$ lands in $\{-1, 0, 1\}$. That check takes microseconds and $4913$ of them take no time at all. The true secret is found.

Every worked example in this book has this property, and it is the same situation as factoring $143$ in Chapter 2. The pencil version is meant to show you the shape of the problem, never to demonstrate its difficulty.

Real parameters close the gap by raising $n$ and $q$ together. ML-KEM uses $q = 3329$ with lattice dimension $256$ per polynomial and two to four polynomials, so the search space is astronomically larger than $4913$, and the error distribution is arranged so that the noise is small relative to $q$ but large enough that no shortcut works.

There is a genuine tension in choosing those parameters. Too much noise and the legitimate recipient cannot decrypt either, because the error swamps the message. Too little and lattice reduction finds the secret. The parameter sets in FIPS 203 and 204 are the outcome of that trade-off, argued out over the eight years of the competition.

04.LWE is a lattice problem wearing a disguise

The connection to the first half of the chapter can be made exact.

Given an LWE instance $(A, b)$, define the set

$$\Lambda_q(A) \;=\; \{\, y \in \mathbb{Z}^m \;:\; y \equiv A s \pmod q \text{ for some } s \in \mathbb{Z}^n \,\} .$$

This is a lattice. It contains every vector that is a valid noiseless product $As$, together with everything congruent to one modulo $q$.

Now look at where $b$ sits. By construction $b = As + e$ with $e$ small. So $As$ is a point of the lattice, and $b$ is that point pushed off by a short distance $\|e\|$.

Recovering $s$ means finding which lattice point $b$ is sitting next to. That is the closest vector problem from Short Vectors: SVP and CVP, in the restricted form where you know in advance that the target is unusually close to the lattice. That restricted form has its own name, bounded-distance decoding.

So the two halves of the chapter meet here. Noise turned linear algebra into geometry.

05.Regev's theorem, and why it is unusual

In 2005 Oded Regev proved the result that gives lattice cryptography a foundation nothing else in the field has.

Solving LWE on randomly chosen instances is at least as hard as solving $\gamma$-approximate SVP on every lattice, in the worst case.

The phrase to focus on is worst case.

Most cryptographic assumptions are statements about average instances. "Factoring a random 2048-bit product of two primes is hard" says nothing about the hardest such number, and it is entirely possible that most instances are hard while the particular one your key generator produced is easy. Choosing parameters badly, or being unlucky, is a real risk, and the history of cryptography contains many keys that turned out to be weak for reasons nobody anticipated.

Regev's reduction removes that category of worry. It says that if you can break a random LWE instance, you can break the worst lattice that exists in that dimension. So there are no weak instances hiding in the distribution. Being unlucky with your randomness cannot hand an attacker an easy key, because an easy random instance would imply an easy worst case, and the worst case is precisely what is assumed hard.

Two honest caveats. The reduction is to $\gamma$-approximate SVP for a specific and fairly large $\gamma$, not to exact SVP, and it does not prove that problem is hard. It relocates the assumption rather than discharging it. And the original reduction was quantum, meaning it used a quantum algorithm as an intermediate step, though later work established classical versions under somewhat different parameters.

What it does deliver is a guarantee that the assumption is concentrated in one place. You have to believe exactly one thing: that approximating the shortest vector in a high-dimensional lattice is hard. Everything else follows.