Lattices and Learning With Errors

Why we need a new kind of hard problem

RSA, Diffie-Hellman and elliptic curves all rest on problems with a hidden periodic structure. As Shor's algorithm showed, a large fault-tolerant quantum computer can find that period efficiently. To replace them, we need problems where no such structure is known to exist.

Lattice problems are the leading candidates. They underpin both ML-KEM (FIPS 203) and ML-DSA (FIPS 204). This lesson builds the core idea, Learning With Errors (LWE), from scratch. You'll encrypt a bit with it, then break the encryption by turning up the noise.

Lattices in one picture

A lattice is every integer combination of a set of basis vectors. In two dimensions, take vectors b1 = (2, 0) and b2 = (1, 2). The lattice is all points x·b1 + y·b2 with integers x, y. The result is an infinite, regular grid of dots, slanted rather than square.

The same lattice has many bases. (2, 0), (1, 2) is a "good" basis: short and nearly perpendicular. (2, 0), (13, 2) generates the exact same grid, because 13 = 1 + 6·2, but its vectors are long and skewed. With a good basis, questions about the lattice are easy. With a bad one, they get hard quickly as the dimension grows.

Two classic questions:

• Shortest Vector Problem (SVP): find the shortest nonzero point in the lattice.
• Closest Vector Problem (CVP): given a point that is not on the lattice, find the nearest lattice point.

In 2 dimensions you can solve these by eye. In 500 or more dimensions, with only a bad basis, the best known classical and quantum algorithms take time exponential in the dimension. Cryptographers rely on that gap. No known quantum algorithm closes it in the way Shor closes the gap for factoring.

Learning With Errors

Oded Regev introduced LWE in 2005. Fix a modulus q and a dimension n. Pick a secret vector s of n numbers mod q. Then publish many samples of the form

b = a · s + e   (mod q)

where each a is a uniformly random vector and each e is a small random error, say between −2 and 2. Stack m samples and you get a matrix equation b = A·s + e (mod q).

The LWE problem: given A and b, find s. (The "decision" version asks you only to tell such b apart from uniformly random numbers. For cryptography, that's the one that matters.)

A worked example

Take q = 17, n = 2 and the secret s = (3, 5). Three samples:

Without the errors, the first two rows give two linear equations in two unknowns. Gaussian elimination mod 17 solves them in a handful of operations. With the errors, every equation is slightly wrong, and elimination amplifies those small errors into garbage. At this toy size you could still brute-force all 17² = 289 candidates. At real sizes, recovering s becomes a close-vector problem on a lattice built from A: b is a point near the lattice, and e is the offset.

Why anyone believes it's hard

Regev proved a remarkable reduction: solving LWE on average, for random instances, is at least as hard as solving certain lattice problems in the worst case, using a quantum algorithm. So if you can break random LWE instances, you can solve every instance of those well-studied lattice problems. That's a much stronger guarantee than "nobody has broken this particular key yet."

Encrypting one bit with LWE

Here is Regev's public-key scheme, in the shape you'll see inside ML-KEM. The public key is (A, b = A·s + e). The secret key is s.

import random
q, n, m = 97, 8, 20                    # toy sizes: NOT secure
s = [random.randrange(q) for _ in range(n)]
A = [[random.randrange(q) for _ in range(n)] for _ in range(m)]
e = [random.randint(-2, 2) for _ in range(m)]
b = [(sum(a*x for a, x in zip(row, s)) + ei) % q for row, ei in zip(A, e)]

def encrypt(bit):
    r = [random.randrange(2) for _ in range(m)]          # random subset of rows
    u = [sum(ri*row[j] for ri, row in zip(r, A)) % q for j in range(n)]
    v = (sum(ri*bi for ri, bi in zip(r, b)) + bit*(q//2)) % q
    return u, v

def decrypt(u, v):
    d = (v - sum(uj*sj for uj, sj in zip(u, s))) % q
    return 1 if q//4 < d <= 3*q//4 else 0                # near q/2 means 1

Why decryption works: expand v − u·s. Every a·s term cancels, leaving

v − u·s = Σ r_i·e_i + bit·⌊q/2⌋   (mod q)

The sum of the selected errors is small. So the result lands near 0 for a 0 bit and near q/2 for a 1 bit. Decryption is correct whenever |Σ r_i·e_i| < q/4, roughly. With m = 20 rows and errors bounded by B, the worst case is 20·B. If 20·B < q/4 ≈ 24.25, decryption always succeeds. Above that, it usually still succeeds, until it doesn't.

That's the central tension of lattice cryptography. More noise makes the problem harder for attackers, but it also makes decryption less reliable. Real parameter sets are tuned so the failure probability is astronomically small: for ML-KEM-768, FIPS 203 gives 2^−164.8.

Try three things. First, set the noise to B = 1 and encrypt 1,000 bits: zero failures, guaranteed. Second, push B to 8 or more and watch the dot on the wheel wander into the wrong half. Third, set B = 0 and click the attack button: Gaussian elimination recovers the secret instantly. With any noise, the same attack returns nonsense.

From LWE to Module-LWE

Plain LWE has an efficiency problem. The public matrix A has m × n entries. At secure dimensions that's hundreds of kilobytes, and multiplying by it is slow. The fix is to give A structure.

Polynomial rings

Work in the ring R_q = Z_q[X]/(Xn + 1): polynomials of degree less than n with coefficients mod q, where you replace Xn by −1 whenever it appears. A single ring element packs n coefficients, and multiplying by it acts like multiplying by a structured n × n matrix. You store n numbers instead of n2.

Ring-LWE and Module-LWE

• Ring-LWE replaces the vector s and matrix A with single ring elements: b = a·s + e in R_q. It's compact, but the structure is rigid, with one ring size per security level.
• Module-LWE is the middle ground: s is a vector of k ring elements and A is a k × k matrix of ring elements. Change k and you change the security level while reusing the same ring arithmetic.

ML-KEM uses Module-LWE with n = 256 and q = 3329 fixed, and k = 2, 3 or 4 for ML-KEM-512, -768 and -1024. Those are NIST security categories 1, 3 and 5. The effective LWE dimension is 256·k: 512, 768 or 1024. The parameter-set names are not a coincidence.

One more space saver: ML-KEM never transmits A. Both sides expand it from a 32-byte public seed with an extendable-output function (SHAKE128). That's how an ML-KEM-768 public key fits in 1,184 bytes.

What attackers actually do

The best known attacks on LWE convert it into a lattice problem and run lattice reduction, such as the BKZ algorithm, which searches for a better (shorter, more orthogonal) basis. Their cost grows exponentially with the dimension. Parameter sets are chosen from detailed cost estimates of these attacks, with margins on top. Quantum computers are only known to give modest, generic speedups to some subroutines. Nothing comparable to Shor is known.

Two practical consequences follow:

• Toy sizes are not "slightly less secure"; they're broken. The widget's n = 8 instance falls to lattice reduction in a blink. Security only appears at hundreds of dimensions.
• Noise is part of the security argument. Implementations that sample noise from the wrong distribution, or reuse randomness, can quietly turn LWE back into linear algebra. You'll meet these failure modes in implementation pitfalls.

Questions

Get five of six right to mark the lesson complete. They also feed the final exam.

Sources

• Regev, On Lattices, Learning with Errors, Random Linear Codes, and Cryptography (2005)
• NIST FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard
• Bos et al., CRYSTALS-Kyber: a CCA-secure module-lattice-based KEM
• NIST FIPS 204: Module-Lattice-Based Digital Signature Standard

Drawn byKyeson Blake Utley

CourseQuantum Defense

Sheet13 of 18

PartIII · Engineer

Rev.18 Oct 2026

Sources4 cited

Found an error?Send a correction