Lattice-Based Cryptography (ML-KEM)
Lattice-based cryptography is the most important family of post-quantum algorithms. ML-KEM — standardized by NIST as FIPS 203 — is the algorithm already being deployed in TLS by Google, Cloudflare, and AWS. Here's the intuition behind the math that makes it quantum-safe.
What is a Lattice?
In mathematics, a lattice is a regular grid of points in a high-dimensional space. Think of it like a 2D grid of dots on a piece of graph paper — but extended to hundreds or thousands of dimensions.
A 2D lattice. Real cryptographic lattices have hundreds or thousands of dimensions — visualizable only in cross-section like this.
Lattices are defined by basis vectors — a set of vectors you can combine (with integer coefficients) to reach any point in the lattice. Like the x and y axes defining all points on graph paper.
The Hard Problems: SVP and LWE
Lattice cryptography is based on two related hard problems:
Shortest Vector Problem (SVP)
Given a lattice, find the shortest non-zero vector in it. Easy in 2D (look at it), computationally infeasible in high dimensions. The best known quantum algorithms provide only modest speedups — far from breaking it.
Learning With Errors (LWE)
Given many equations of the form: b = a·s + e (mod q) where a and b are known, but s (the secret) and e (tiny random noise/error) are hidden — recover s.
The noise "e" is what makes this hard. Without noise, solving is easy (linear algebra). With small random noise, it becomes infeasible even for quantum computers.
LWE Intuition: Math With Noise
Here's a simplified analogy for LWE. Suppose your secret is a combination to a safe: s = [3, 7, 2].
I give you many hints like:
- 2×3 + 5×7 + 1×2 + noise ≈ 43.1 (true answer is 43)
- 4×3 + 1×7 + 6×2 + noise ≈ 32.8 (true answer is 31)
- 1×3 + 3×7 + 2×2 + noise ≈ 30.2 (true answer is 28)
The noise is small and random, but it corrupts every hint just enough to make the system overdetermined and noisy — impossible to solve directly with linear algebra. In real LWE, the numbers operate in modular arithmetic, the vectors have hundreds of entries, and the noise is carefully calibrated to be small enough that legitimate parties can work with it but large enough to defeat attacks.
How ML-KEM Uses Lattices for Key Exchange
Key Generation
The server generates a random lattice-based "public matrix" A and a random secret vector s, plus some noise e. The public key is essentially (A, A·s + e mod q). The private key is s.
Encapsulation (client)
The client generates its own random vector r (with noise), and uses the server's public key to compute an "encryption" of a random shared secret K. The client sends this ciphertext to the server.
Decapsulation (server)
The server uses its private key s to remove the main structure from the ciphertext and recover K — the noise is small enough that it can be rounded away, revealing the exact shared secret. The client and server now share K without it ever being transmitted in the clear.
ML-KEM Performance: Surprisingly Fast
One reason ML-KEM won the NIST competition is its excellent performance profile:
ML-KEM-768 is significantly faster than RSA-2048 for key exchange, and comparable to ECDH. The main cost is larger key sizes — but for TLS, this adds only a few hundred extra bytes to the handshake, which is generally acceptable.
Frequently Asked Questions
What's the "Module" in "Module-LWE"?
Plain LWE uses a single long vector as the secret. Module-LWE (M-LWE) structures the secret as a matrix of shorter polynomial-based elements — using polynomial rings. This "module" structure makes the math more efficient (faster with smaller parameters) while maintaining the same security reductions. ML-KEM and ML-DSA both use Module-LWE as their foundation, hence the "ML" prefix.
Has any quantum algorithm been shown to speed up attacks on lattice problems?
Quantum computers provide some speedup for lattice algorithms — specifically, quantum speedups for some subroutines used in the best lattice solvers. However, the speedup is much more modest than Shor's exponential advantage over RSA. The best known quantum attacks on LWE provide only a marginal improvement over classical attacks, and the NIST parameter sets were selected with this quantum speedup accounted for.
Frequently Asked Questions
What will I learn here?
This page covers the core concepts and techniques you need to understand the topic and progress confidently to the next lesson.
How should I use this page?
Start with the overview, then follow the section links to deepen your understanding. Use the table of contents on the right to jump to specific sections.
What should I read next?
Use the navigation below to continue to the next lesson or explore related topics.