Lattices and learning with errors

ML-KEM and ML-DSA rest on learning with errors: linear equations with a little noise added. Without the noise, Gaussian elimination solves them instantly. With it, the best known attacks turn the problem into finding a short vector in a lattice. This note does that on a small instance and measures where it stops working.

Instance shown
n = 6 unknowns, m = 12 equations, q = 31, centred binomial noise with η = 2
Attack
Primal embedding into a lattice of dimension 13, reduced with LLL (δ = 0.99)
Result
Secret recovered after 200 LLL swaps, and checked
Where LLL stops
Success falls from certain at small n to 1 in 6 at n = 32

Lattices

A lattice is the set of all integer combinations of some linearly independent vectors b1, …, bd in Rd. Those vectors are a basis, and every lattice of dimension two or more has infinitely many bases. Some are made of short, nearly orthogonal vectors, and others of long vectors that point in almost the same direction. The lattice is the same either way, but what you can compute with it is not.

The central problems are about short vectors. The shortest vector problem (SVP) asks for the shortest non-zero vector in the lattice, and the closest vector problem (CVP) for the lattice vector nearest a given point. With a good basis both are easy to approximate. With a bad basis, and in high dimension, no known algorithm, classical or quantum, finds them in less than exponential time.

Lattice reduction is the process of turning a bad basis into a better one. The LLL algorithm of Lenstra, Lenstra and Lovász, from 1982, runs in polynomial time and returns a basis whose first vector is within a factor exponential in d of the shortest. In the worst case that factor is 2(d−1)/2. In practice LLL does far better than its guarantee: Gama and Nguyen measured the first vector at about 1.02d times the expected length of the shortest vector. That gap between guarantee and practice runs through all of lattice cryptanalysis. Security estimates are built on measured behaviour and models of it, not on theorems.

Learning with errors

Regev's learning with errors problem, from 2005, is this. A secret vector s of length n has small entries. You are given a random m × n matrix A over Zq and

b = A s + e  (mod q) An LWE instance: e is a vector of small errors

and you must find s. Here is one with n = 6, m = 12 and q = 31. The entries of s and e are drawn from the centred binomial distribution with η = 2, the same noise distribution ML-KEM uses, so each entry is between −2 and 2 and most are 0 or ±1:

14   1  27  30  25  11   |   4
23  16  27   8  26   5   |   2
 9  22  17  10  20  25   |  16
17  26  26   1  11   1   |  25
28   9   2   9   6   0   |   7
15  16  20  12  27  26   |  27
23  28  29  21  24  18   |  12
20  23  27   1   8   0   |  25
 8  25  22  10  24   6   |  24
10  19  15  25  30  20   |  26
20  12  11   5  30   2   |  25
24  20  25  19   1   1   |  17

A (12 × 6) and b = As + e mod 31

The secret is s = (0, 1, -2, 1, -1, -1) and the error is e = (1, 1, 1, 0, -1, -1, 1, 1, 1, 0, 0, -1). Neither is known to the attacker.

Without the error this would be trivial. The first 6 equations alone determine s, by Gaussian elimination. Doing exactly that here gives the candidate (10, 13, -3, 9, 0, -11). It satisfies those first 6 equations perfectly, and misses the remaining equations by amounts as large as 11: the residuals b − As, reduced into the range around zero, are (0, 0, 0, 0, 0, 0, 10, 1, 2, -2, -11, -10). Gaussian elimination carries the error forward and amplifies it, and a single wrong entry of the result is as bad as all of them.

Brute force does work at this size. There are 56 = 15,625 possible secrets, and each can be tested by checking that b − As is small. At ML-KEM's sizes that search is over 5512 or more, and not an option.

The primal attack

The standard attack turns the instance into a lattice problem. The vectors As mod q, for every s, together with all multiples of q, form a lattice of dimension m. The vector b lies very close to one of its points, namely As, because b − As = e is small. Finding s is therefore a closest-vector problem, and Kannan's embedding turns it into a shortest-vector problem: add b as one more basis vector, with an extra coordinate set to 1. The lattice then contains (b − As, 1) = (e, 1), which is far shorter than a lattice of that dimension and determinant would normally hold.

  1. Build the basis. Each vector As mod q is fixed by its first n coordinates, so the lattice has a basis of n rows [I | (A2A1−1)T] and m − n rows that are q times a unit vector, where A1 is the top n × n block of A. The row (b, 1) is appended to them. Here that is 13 rows in dimension 13.
  2. Reduce it. LLL with δ = 0.99, in exact integer arithmetic, took 200 swaps.
  3. Read off the error. The reduced basis contains (1, 1, 1, 0, -1, -1, 1, 1, 1, 0, 0, -1, 1). Its last coordinate is 1, so its first 12 coordinates are a candidate error vector. Its length is 3.16; the next shortest vector in the reduced basis has length 3.46.
  4. Recover and check. The candidate gives b1 − e1 = A1s, so s = A1−1(b1 − e1) = (0, 1, -2, 1, -1, -1). The attacker accepts it because s and b − As are both small in every coordinate, a test that needs no knowledge of the answer. It matches the real secret.

The code runs one further check: it verifies both LLL conditions on the reduced basis exactly, with rational Gram–Schmidt, so the reduction itself is checked rather than trusted. The (e, 1) vector here is only slightly shorter than the next one, which is one sign that this instance sits near the edge of what LLL can do.

Where LLL stops

The attack works when the embedded error vector is short enough, relative to the lattice, that the reduction algorithm finds it. As the dimension grows with q and the noise fixed, the gap closes and LLL's approximation factor of about 1.02d is no longer good enough. Repeating the attack on fresh instances shows where that happens:

The primal attack with LLL (δ = 0.99) against LWE with q = 31, m = 2n, and centred binomial noise with η = 2. 6 fresh instances per row. Success means the attack returned the secret and it was checked.
nLattice dimensionSecret recoveredMean LLL swaps
8176 of 6405
14296 of 61,789
20415 of 64,106
26531 of 66,847
32651 of 69,608

Recovery is certain at small n, first fails at n = 20, and by n = 32, a lattice of dimension 65, it succeeds 1 time in 6. The failures are not partial: when LLL does not surface (e, 1), the reduced basis contains nothing that passes the attacker's check. The number of swaps grows quickly with the dimension.

Past this point the attacker switches from LLL to BKZ, which reduces the basis in overlapping blocks of dimension β and calls an exact SVP solver on each. A larger β gives a shorter vector, and costs exponentially more. With the best lattice sieves, one call in dimension β costs about 20.292β classical operations (Becker, Ducas, Gama and Laarhoven). Security estimates for LWE therefore ask what block size β the attack needs, then price one or more SVP calls at that size. That price is the "core-SVP" figure quoted for lattice schemes. The Lattice Estimator of Albrecht, Player, Scott and others automates the calculation, for the primal attack shown here and for the dual and hybrid attacks alongside it.

From here to ML-KEM

ML-KEM uses the same noise with q = 3329, and a secret of dimension 512, 768 or 1024 made of polynomial blocks: module LWE, which saves space and time without, as far as anyone knows, helping the attacker. At those sizes the primal attack still applies. It needs a block size in the hundreds, far beyond anything computed, and its cost is estimated rather than measured, which is where the debates about ML-KEM-512's margin come from. ML-DSA rests on module LWE and on a second problem, module SIS, which asks for short solutions to linear equations and is attacked with the same reduction algorithms.

The same machinery also breaks schemes that were never meant to be lattice-based. When a few bits of an ECDSA nonce leak, the hidden number problem becomes a closest-vector problem, and LLL or BKZ recovers the private key from enough signatures.

Primary sources

  1. A. K. Lenstra, H. W. Lenstra and L. Lovász, "Factoring polynomials with rational coefficients", Mathematische Annalen 261 (1982)
  2. O. Regev, "On lattices, learning with errors, random linear codes, and cryptography", Journal of the ACM 56 (2009)
  3. N. Gama and P. Q. Nguyen, "Predicting lattice reduction", EUROCRYPT 2008
  4. M. R. Albrecht, R. Player and S. Scott, "On the concrete hardness of learning with errors", Journal of Mathematical Cryptology 9 (2015)
  5. A. Becker, L. Ducas, N. Gama and T. Laarhoven, "New directions in nearest neighbor searching with applications to lattice sieving", SODA 2016
  6. H. Cohen, A Course in Computational Algebraic Number Theory, Springer (1993), Algorithm 2.6.7 (integral LLL, as implemented here)
  7. The Lattice Estimator