Jorge Quitério Search
IT & Engineering

Learning with errors and post-quantum key exchange

ML-KEM, the new standard for quantum-resistant key exchange, rests on a statistical problem: recovering a secret from linear equations deliberately perturbed by small random errors. A simulation shows how increasing noise leads to decryption failure.

Consider a system of linear equations whose right-hand sides have each been perturbed by a small random number. Without knowledge of the solution the system cannot be solved, but whoever knows the solution can still verify answers and transmit information through the noise.

This is essentially the principle of the new generation of public-key cryptography.

Most public-key cryptography in use today rests on number theory: factoring (RSA) and discrete logarithms on elliptic curves. Shor's algorithm breaks both on a large quantum computer, which is why the migration I described in planning the migration to post-quantum cryptography is necessary. The replacement for key exchange, ML-KEM, rests on linear algebra with noise. This article explains why the noise is simultaneously the source of security and the source of risk, and illustrates the boundary between them.

The scheme is already in everyday use. The major web browsers use ML-KEM, combined with a classical algorithm, when connecting to websites that support it, so a large share of ordinary web traffic is protected in this way without users noticing.

The relevant literature is as follows.

Regev (2005; journal version 2009) introduced the learning with errors (LWE) problem and a public-key scheme built on it. He also gave a quantum reduction showing that solving LWE on average would solve certain lattice problems in the worst case, a rare kind of guarantee in cryptography.

Lenstra, Lenstra and Lovász (1982) gave the LLL algorithm for finding short vectors in lattices. It and its descendants are the main tools for attacking LWE, and for well-chosen parameters they need exponential time.

The CRYSTALS-Kyber specification (Avanzi and colleagues, version 3.02, 2021) describes the scheme submitted to the NIST competition, including its decryption-failure analysis.

NIST FIPS 203 (August 2024) standardised it as ML-KEM, in three parameter sets: ML-KEM-512, -768 and -1024.

Learning with errors

Take a secret vector s\mathbf{s} of length nn with entries modulo a prime qq. Publish many random vectors ai\mathbf{a}_i together with

bi=⟨ai,s⟩+ei(modq), b_i = \langle \mathbf{a}_i, \mathbf{s} \rangle + e_i \pmod q ,

where each eie_i is a small random error. The LWE problem is to recover s\mathbf{s}.

Without the errors this is elementary linear algebra: nn equations solved by Gaussian elimination. With the errors, elimination fails, because every step adds and multiplies equations and therefore adds and multiplies their noise. After a few steps the noise is larger than the signal.

LWE as a statistical problem

Read as statistics, LWE is a regression: the ai\mathbf{a}_i are regressors, s\mathbf{s} the coefficients, eie_i the error term. The difference is the reduction modulo qq, which wraps everything around a circle and destroys the geometry least squares relies on.

Supermarket receipts make the contrast concrete. Estimating the price of each product from a pile of receipts is ordinary regression: even if every total were off by a few cents, enough receipts would recover the prices accurately. If each total were also printed only as its remainder after division by some large number, the totals would carry no usable size information, and averaging over many receipts would no longer help. That combination of small noise and wrapped arithmetic is what LWE adds.

The decision version is a hypothesis test: are these pairs LWE samples or uniformly random? Security means no efficient test does better than chance. The distance between those two distributions, the subject of Kullback-Leibler divergence and Hellinger distance, bounds any attacker's advantage.

Decryption

In Regev-style encryption the public key is a matrix AA and b=As+e\mathbf{b} = A\mathbf{s} + \mathbf{e}. To encrypt a bit μ\mu, pick a random subset of the equations (a 0/1 vector r\mathbf{r}) and send

u=r⊤A,v=r⊤b+μ⌊q2⌋. \mathbf{u} = \mathbf{r}^\top A, \qquad v = \mathbf{r}^\top \mathbf{b} + \mu \left\lfloor \tfrac{q}{2} \right\rfloor .

The holder of s\mathbf{s} computes v−u⋅s=r⊤e+μ⌊q/2⌋v - \mathbf{u}\cdot\mathbf{s} = \mathbf{r}^\top \mathbf{e} + \mu \lfloor q/2 \rfloor. Consider a clock with q=3,329q = 3{,}329 hours: a 0 is hidden near midnight and a 1 near half past, each nudged by the sum of the noise of the chosen equations. Decryption reads whichever is closer.

In a toy Python version with a secret of length 16, 64 public equations and small errors, 2,000 encryptions all decrypted correctly; the accumulated noise had a standard deviation of about 6, against a margin of q/4≈832q/4 \approx 832. This example is far too small to be secure; it only illustrates the mechanism.

Noise, security and decryption failure

  • Too little noise and the equations become solvable: security collapses.
  • Too much noise and the accumulated sum occasionally crosses the margin: a legitimate decryption fails.

ML-KEM fixes the trade-off with the centred binomial distribution: the difference of two sums of η\eta fair coin flips, with values between −η-\eta and η\eta and variance η/2\eta/2. It is cheap to sample in constant time and has light tails. ML-KEM works over polynomial rings (module LWE) with n=256n = 256, q=3329q = 3329, module rank 2, 3 or 4, and η\eta of 2 or 3. The designers put the decryption failure probability at roughly 2−1392^{-139}, 2−1652^{-165} and 2−1752^{-175} for the three parameter sets. These are computed tail probabilities, far too small to be observed experimentally.

The figure below varies the noise. Decryption works as long as the accumulated noise stays well inside a quarter of the clock, and the failure rate follows a normal tail that can be computed in advance.

Each dot is one of 1,000 encryptions of a random bit, placed where it lands on the clock after decryption. Green dots were read correctly; orange ones were not.

Suggested settings:

  1. Small example. With noise 1 and 64 equations, the accumulated noise is about 5.7, and every dot sits tightly at midnight or half past. Zero failures.
  2. Onset of failures. Raise the noise per equation slowly. Around 50, the first failures appear (predicted about 0.3%). Around 73, the accumulated noise is about half the margin and the predicted failure rate is about 4%: the observed count out of 1,000 lands close to 44.
  3. Excessive noise. Push the noise to the maximum. The dots smear around the whole clock and the failure rate approaches 50%: decryption becomes equivalent to guessing.
  4. More equations. Go back to a working noise level and increase the number of equations. Failures rise, because each ciphertext sums the noise of more equations. Real schemes balance key size, security and correctness at the same time.

Derivation of the failure rate. Each equation is included with probability 1/2, and the errors are independent with standard deviation σ\sigma, so the accumulated noise has variance about mσ2/2m\sigma^2/2. By the central limit theorem it is approximately normal, and a bit is misread when it lands more than q/4q/4 from where it should be, after wrapping around the clock. The widget's prediction is therefore

P(fail)=1−∑j[Φ ⁣(q/4−jqσacc)−Φ ⁣(−q/4−jqσacc)],σacc=σm/2, P(\text{fail}) = 1 - \sum_{j} \left[\Phi\!\left(\frac{q/4 - jq}{\sigma_{\text{acc}}}\right) - \Phi\!\left(\frac{-q/4 - jq}{\sigma_{\text{acc}}}\right)\right], \qquad \sigma_{\text{acc}} = \sigma\sqrt{m/2},

which is about 2Φ(−832/σacc)2\Phi(-832/\sigma_{\text{acc}}) when the noise is small, and tends to 1/2 when the noise is so large that the position on the clock is uniform.

The new primitives should not be treated as black boxes. Their security and their correctness both depend on carefully calibrated randomness. For engineers this implies:

  • Noise sampling is security-critical code. An implementation that samples the noise badly, or leaks it, breaks the scheme even if the mathematics is sound.
  • Constant time is a requirement. Several published attacks on early lattice implementations exploited timing or decryption failures.
  • Tails matter. The design rests on bounding a rare event. It is the same idea as heavy-tailed errors, in reverse: here the lightness of the tail is what makes the protocol work.

References

  1. O. Regev, "On lattices, learning with errors, random linear codes, and cryptography", Journal of the ACM, 56(6), article 34, 2009 (conference version STOC 2005).
  2. A. K. Lenstra, H. W. Lenstra and L. Lovász, "Factoring polynomials with rational coefficients", Mathematische Annalen, 261, 515-534, 1982.
  3. R. Avanzi, J. Bos, L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, J. M. Schanck, P. Schwabe, G. Seiler and D. Stehlé, CRYSTALS-Kyber: Algorithm Specifications and Supporting Documentation, version 3.02, 2021.
  4. NIST, FIPS 203, Module-Lattice-Based Key-Encapsulation Mechanism Standard, August 2024.