Post-quantum cryptography: After Shor: lattices, ML-KEM and ML-DSA

In 1994 Peter Shor, at Bell Labs, showed that a quantum computer could factor integers and compute discrete logarithms in polynomial time. Every public-key system in common use (RSA, finite-field and elliptic-curve Diffie–Hellman, ECDSA, Ed25519) rests on one of those two problems. The machine needed does not exist yet: today's quantum processors have hundreds or a few thousand noisy qubits, and breaking RSA-2048 needs on the order of a million of them, run with error correction for days. But cryptography has to plan for decades, and an adversary can harvest now and decrypt later: record encrypted traffic today and read it once the machine exists. Secrets that must last ten years are already at risk.

What a quantum computer breaks

Theorem (Shor, 1994)

A quantum computer can factor an $n$ -bit integer, and compute discrete logarithms in any group where the group operation is efficient (including elliptic curves), in time polynomial in $n$ , roughly $O (n^{3})$ gates.

The key idea is to turn the problem into finding the period of a function such as $x \mapsto a^{x} mod N$ , and to find periods with the quantum Fourier transform. The sister site Math of Quantum develops the whole algorithm. Resource estimates keep falling: in 2019 Craig Gidney and Martin Ekerå estimated 20 million noisy qubits for eight hours; in 2025 Gidney brought it below one million qubits in under a week.

What it barely touches

Symmetric cryptography is much less exposed.

Theorem (Grover 1996; Bennett, Bernstein, Brassard, Vazirani 1997)

A quantum computer can find one marked element among $N$ with about $\frac{π}{4} \sqrt{N}$ queries, and no quantum algorithm can do it with asymptotically fewer.

So a key search on a $k$ -bit cipher drops from $2^{k}$ to about $2^{k / 2}$ , and only in theory: Grover's iterations are sequential and cannot be spread over many machines without losing the advantage. Doubling key sizes is enough: AES-256 and SHA-384 or SHA-512 are considered safe against quantum attack. Hash-function collisions gain even less.

Mathematics that resists

The replacements must use problems for which no quantum algorithm is known. Several families had been studied for decades:

Codes. Robert McEliece's 1978 cryptosystem hides a message as a codeword of a secret error-correcting code plus deliberate errors; decoding a random-looking linear code is hard. It has never been broken, but its public keys are around a megabyte.
Hash-based signatures. Leslie Lamport's one-time signatures (1979), combined into Merkle trees, rest only on the security of a hash function. SPHINCS+ (now SLH-DSA) is the conservative choice: large, slow signatures, minimal assumptions.
Multivariate systems of quadratic equations, and isogenies between elliptic curves. SIKE, an isogeny scheme in the final round of the competition, was broken in July 2022 by Wouter Castryck and Thomas Decru in about an hour on a laptop, using a 1997 theorem of Ernst Kani: a reminder of why candidates are attacked in public for years.
Lattices, which won.

NIST opened its competition in 2016 and received 82 submissions. In 2022 it chose CRYSTALS-Kyber for key establishment and CRYSTALS-Dilithium, Falcon and SPHINCS+ for signatures. In August 2024 the first three standards were published: FIPS 203 (ML-KEM), FIPS 204 (ML-DSA) and FIPS 205 (SLH-DSA); in March 2025 NIST added the code-based HQC as a backup KEM.

Lattices

Definition (lattice)

Given linearly independent vectors $b_{1}, \dots, b_{n} \in ℝ^{n}$ (a basis), the lattice they generate is the set of all their integer combinations, $ℒ = {x_{1} b_{1} + \dots + x_{n} b_{n} : x_{i} \in ℤ}$ : a regular grid of points.

The same lattice has infinitely many bases: multiplying a basis by an integer matrix of determinant $\pm 1$ gives another. Some bases are good (short, nearly orthogonal vectors) and some are bad (long, nearly parallel). Two problems are believed hard in high dimension, for classical and quantum computers alike:

Shortest Vector Problem (SVP): find a shortest non-zero vector of $ℒ$ .
Closest Vector Problem (CVP): given a point $t$ , find the lattice point closest to it.

With a good basis, CVP is easy in practice: write $t$ in the basis and round each coordinate (László Babai's rounding, 1986). With a bad basis, rounding lands far away. That asymmetry is a trapdoor: the good basis is the private key, a bad basis of the same lattice the public one (the GGH idea of Goldreich, Goldwasser and Halevi, 1997). Miklós Ajtai proved in 1996 something unusual for cryptography: certain random lattice problems are as hard as the worst case of approximate SVP.

The same two-dimensional lattice with two bases. Click to place a target point. With the good basis, Babai's rounding finds the closest lattice point; with the bad basis (same lattice, long nearly parallel vectors), rounding lands on a distant point. In two dimensions you can see the right answer; in the 768 dimensions of ML-KEM, nobody can.

Learning with errors

In 2005 Oded Regev introduced the problem on which ML-KEM and ML-DSA are built.

Definition (LWE)

Fix a modulus $q$ , a dimension $n$ and a secret $s \in ℤ_{q}^{n}$ . An LWE sample is a pair $(a, ⟨ a, s ⟩ + e)$ , with $a$ uniform in $ℤ_{q}^{n}$ and $e$ a small random error. The problem is to recover $s$ (or just to distinguish such samples from uniformly random pairs) given many of them. In matrix form: given $A$ and $b = A s + e mod q$ , find $s$ .

Without the error, $b = A s$ is a linear system, solved by Gaussian elimination. The small error makes it, as far as anyone knows, hopeless: it is a CVP instance in a lattice built from $A$ .

Theorem (Regev, 2005)

For suitable parameters (Gaussian errors of size about $α q \geq 2 \sqrt{n}$ ), solving LWE on average is at least as hard as solving approximate SVP and related lattice problems in the worst case, by a quantum reduction.

Regev's public-key encryption of a bit is short enough to write down. The public key is $(A, b = A s + e)$ with $m$ rows. To encrypt a bit $μ$ , pick a random subset $S$ of the rows and send

u = \sum_{i \in S} a_{i}, v = \sum_{i \in S} b_{i} + μ ⌊ \frac{q}{2} ⌋ (\mod q) .

To decrypt, compute $v - ⟨ u, s ⟩$ and output 0 if it is closer to 0 than to $q / 2$ , and 1 otherwise.

Proposition (correctness)

$v - ⟨ u, s ⟩ = μ ⌊ q / 2 ⌋ + \sum_{i \in S} e_{i} (\mod q)$ . So decryption is correct whenever $| \sum_{i \in S} e_{i} | < q / 4$ .

Proof

$\sum_{i \in S} b_{i} = \sum_{i \in S} (⟨ a_{i}, s ⟩ + e_{i}) = ⟨ u, s ⟩ + \sum_{i \in S} e_{i}$ , so subtracting $⟨ u, s ⟩$ leaves the message term plus the accumulated error. If the error stays below $q / 4$ in absolute value, the result is on the correct side of the circle $ℤ_{q}$ .

A toy LWE cipher (dimension 8, 24 samples,

q = 401

) encrypting your message bit by bit. Each dot is one decrypted bit placed on the circle

ℤ_{q}

at the value

v - ⟨ u, s ⟩

: bits 0 cluster near 0 and bits 1 near

q / 2

. Turn up the noise: the clusters spread, cross the boundary at

q / 4

, and bits start to flip. Real parameters keep the probability of a decryption failure below

2^{- 138}

Regev received the Gödel Prize in 2018 for this work. Plain LWE has big keys ( $n \times m$ numbers). The standards use module-LWE, where the entries of $A$ , $s$ and $e$ are polynomials in $ℤ_{q} [x] / (x^{256} + 1)$ , multiplied fast with the number-theoretic transform: the same security reductions, keys of about a kilobyte.

ML-KEM

ML-KEM (formerly CRYSTALS-Kyber, by Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz and others) is a key encapsulation mechanism: rather than encrypting a message, it produces a fresh random 32-byte secret together with a ciphertext (“encapsulation”) that only the private key can open. The secret then keys a symmetric cipher. A Fujisaki–Okamoto transform turns the basic LWE encryption into a KEM secure against chosen-ciphertext attacks. ML-KEM-768, the recommended level (about AES-192 strength), has a 1,184-byte public key and a 1,088-byte ciphertext, and it is faster than X25519.

Deployment was quick, and hybrid: combining ML-KEM with X25519, so the connection is safe if either one holds. Chrome and Cloudflare enabled X25519+Kyber in 2023–2024; Signal added PQXDH in 2023 and Apple's iMessage PQ3 in 2024; OpenSSH 10 (2025) made mlkem768x25519 its default key exchange. By 2025 more than a third of the human web traffic seen by Cloudflare was post-quantum. The desktop app's “ML-KEM-768 + AES-GCM” encapsulates a key with ML-KEM and encrypts with AES-256-GCM, with real FIPS 203 keys.

ML-DSA

ML-DSA (formerly CRYSTALS-Dilithium) signs with module lattices by the “Fiat–Shamir with aborts” technique of Vadim Lyubashevsky: the signer proves knowledge of a short secret, and restarts whenever the signature would leak information about it. ML-DSA-65 has a 1,952-byte public key and 3,309-byte signatures, about fifty times Ed25519's, which is the main cost of the migration: certificate chains get much larger. FN-DSA (Falcon) gives smaller signatures with more delicate floating-point arithmetic; SLH-DSA gives the most conservative security at the cost of 8 to 50 KB signatures.

The migration

The US NSA's CNSA 2.0 suite (2022) requires post-quantum algorithms in national-security systems between 2025 and 2033. NIST's transition plan (IR 8547, 2024) deprecates RSA and elliptic curves at 112-bit security in 2030 and disallows them entirely in 2035. The lesson of DES, MD5 and SHA-1 is that migrations take a decade or more; this one has started early, and it is the first time the cryptographic community has replaced its public-key algorithms before they were broken.

The story that began with Caesar's three-letter shift ends, for now, here: with a secret hidden in a lattice of 768 dimensions behind a little noise. The history page puts all of it on one line, and the app lets you try it, from Caesar to ML-KEM, on your own data.

§What a quantum computer breaks

§What it barely touches

§Mathematics that resists

§Lattices

§Learning with errors

§ML-KEM

§ML-DSA

§The migration

§Further reading