03 — Learning With Errors (LWE)

The Puzzle

Imagine a game:

1. I pick a secret vector s with 256 numbers (each between 0 and some modulus q).

2. I generate many random vectors a₁, a₂, ..., aₙ (also 256 numbers each).

3. For each aᵢ, I compute:

   $\displaystyle b_i = \mathbf{a}_i \cdot \mathbf{s} + e_i \pmod q$

   where eᵢ is a small random error (much smaller than q).

4. I give you all pairs (aᵢ, bᵢ) but keep s secret.

Your task: Find the secret s.

Why It's Hard

Without the error eᵢ, this is just a system of linear equations. You'd solve it with Gaussian elimination in polynomial time.

But the error makes it noisy:

• Each bᵢ is slightly wrong
• Gaussian elimination amplifies the errors
• The more equations you use, the more the errors compound

Analogy

Imagine measuring star positions with a telescope that has slight jitter:

• One measurement: you can average out the jitter
• 10,000 measurements: the jitter accumulates faster than the signal
• Finding the "true" star map from noisy observations is extremely hard

The Math

Parameters

The Problem Statement

Given (A, b) where:

• A is an m×n matrix of uniform random numbers mod q
• b = A·s + e mod q
• s is secret (uniform random)
• e is secret (small random, each element from a narrow distribution)

Find s.

Reduction to Lattice Problems

Regev proved (2009): if you can solve LWE efficiently, you can solve approximate SVP in lattices.

Since SVP is believed to be hard:

• LWE is hard → ML-KEM is secure
• This holds for both classical and quantum computers

From LWE to Module-LWE

Pure LWE needs very large keys (megabytes). Module-LWE makes it practical:

The Idea

Instead of vectors of numbers, use vectors of polynomials:

• Work in a ring: polynomials mod (X^256 + 1) with coefficients mod q
• A "module" is like a vector where each element is a polynomial
• Secret s is a small vector of polynomials
• Each aᵢ is a random polynomial

Benefits

ML-KEM uses Module-LWE over the ring R_q = Z_q[X]/(X^256 + 1).

The NTT Speed-Up

Module-LWE enables the Number Theoretic Transform (NTT) — a fast Fourier transform over finite fields:

• Polynomial multiplication: O(n²) naively
• With NTT: O(n log n)
• For n=256: ~50x faster

This is why ML-KEM is faster than RSA despite using larger keys.

Resources

• Regev, "On lattices, learning with errors, random linear codes, and cryptography" (2009), J. ACM.
• Lyubashevsky et al., "On ideal lattices and learning with errors over rings" (2010), Eurocrypt.
• Alkim et al., "Post-quantum key exchange — A new hope" (2016), USENIX Security. [Predecessor to Kyber]