133
Part Three · C · Complexity and cryptography

Post-quantum cryptography: lattice, code, and hash-based schemes, plus standardization

The real defence against Shor’s algorithm is not quantum hardware. It is new mathematics: public-key schemes built on problems that, as far as anyone knows, quantum computers cannot solve either. This post-quantum cryptography runs on ordinary computers and is already deployed in web browsers and messaging apps. In August 2024 the US National Institute of Standards and Technology (NIST) published the first standards, and in October 2026 it set the schedule for retiring RSA and elliptic curves.

On the plate: a toy lattice encryption you can break when it is small and cannot when it is not.

Why urgency, and what Grover does

An adversary can record encrypted traffic today and decrypt it once a large quantum computer exists: harvest now, decrypt later. Medical records and state secrets must stay confidential for decades, so the migration has to finish well before such a machine appears. Symmetric ciphers fare better: Grover’s search (Chapter 115) finds a kk-bit key in about 2k/22^{k/2} steps, so AES-128 drops to roughly 64-bit security against an idealized attacker, and moving to AES-256 restores the margin. Grover’s steps are also sequential and expensive to error-correct, so the practical threat is smaller still. Established

Learning with errors

Oded Regev introduced the learning with errors (LWE) problem in 2005: given many noisy equations bi=ai⋅s+ei(modq)b_i = \mathbf a_i\cdot\mathbf s + e_i \pmod q with small random errors eie_i, find the secret s\mathbf s. Without the errors, Gaussian elimination solves it instantly. With them, the best known classical and quantum algorithms take exponential time in the dimension, and Regev proved that solving it on average is as hard as worst-case problems on lattices. To encrypt a bit, add a random subset of the public equations and shift by q/2q/2 for a 1; the secret holder subtracts u⋅s\mathbf u\cdot\mathbf s and checks whether the result is near 0 or near q/2q/2.

Choose the dimension n=n = 2 with q=97q = 97, and . There are 97n97^n possible secrets. At n=3n = 3 that is under a million and the attack succeeds; at n=12n = 12 it would take millennia. ML-KEM (formerly Kyber, FIPS 203) uses a structured “module” version with q=3329q = 3329 and effective dimension 512 to 1024. Established

Signatures, standards, and broken candidates

ML-DSA (Dilithium, FIPS 204) is a lattice signature. SLH-DSA (SPHINCS+, FIPS 205) relies only on hash functions, descendants of Leslie Lamport’s 1979 one-time signature: publish hashes of 256 pairs of secret strings, and sign by revealing one string from each pair according to the message’s hash bits. with a 16-bit toy. Hash-based signatures are large but rest on the most conservative assumption in cryptography. NIST chose the code-based HQC as a backup key exchange in March 2025; FN-DSA (Falcon, FIPS 206) is in draft. NIST IR 8547, final on 27 October 2026, deprecates RSA and elliptic-curve cryptography at 112-bit security after 2030 and disallows them after 2035.

Humility is built in. In 2022 Ward Beullens broke Rainbow, a finalist signature, in a weekend on a laptop, and Wouter Castryck and Thomas Decru broke SIKE, an isogeny-based finalist, in about an hour on a single core, using mathematics from 1997. Neither break was quantum. That is why standards come with diverse backups. Established

What you now have

Harvest-now-decrypt-later, Grover’s effect on symmetric keys, learning with errors and a working toy, ML-KEM, ML-DSA and SLH-DSA, Lamport signatures, HQC, the NIST timeline, and the lessons of SIKE and Rainbow.

· · ·

Three questions to carry with you.

Why is LWE hard but plain linear equations easy?tap
The small errors defeat Gaussian elimination; the best attacks are lattice reduction, exponential in dimension.
How long should a symmetric key be against Grover?tap
256 bits gives about 128-bit quantum security.
Why were SIKE and Rainbow broken classically?tap
New mathematical attacks on their specific structure; quantum computers played no part.

And one to work out. Grover search for an AES-128 key needs about 2x2^x iterations. What is xx?

x =

Sources: O. Regev, J. ACM 56, 34 (2009) (STOC 2005). C. Peikert, Found. Trends Theor. Comput. Sci. 10, 283 (2016). D. J. Bernstein and T. Lange, Nature 549, 188 (2017). NIST FIPS 203, 204, 205 (August 2024). NIST IR 8547 (final, 27 October 2026). W. Castryck and T. Decru, Eurocrypt 2023, 423. W. Beullens, Crypto 2022, 464. L. Lamport, SRI Tech. Rep. CSL-98 (1979). Checked by code: brute-force recovery of the toy secret for n ≤ 3.

Next · Chapter 134
Quantum money, certified randomness, secure computation

In 2025, a quantum computer accessed over the internet produced randomness that a classical computer could not have faked, under stated assumptions.

Turn the page