Chapter IX
The frontier
Quantum computers, noisy lattices, proofs that reveal nothing, and computing on data you cannot see.
The quantum threat
Shor’s algorithm would break RSA, Diffie-Hellman and elliptic curves. Grover only halves symmetric strength, so AES-256 stays safe.
Public-key cryptography rests on factoring (RSA) and discrete logarithms (Diffie-Hellman, elliptic curves). Shor’s algorithm solves both in polynomial time; to factor N, it finds the period of ax mod N.
Traffic recorded today can be decrypted once one exists (“harvest now, decrypt later”): key exchange migrates first.
Post-quantum standards
ML-KEM for key exchange, ML-DSA and SLH-DSA for signatures: NIST’s 2024 standards. Only ML-KEM is in wide use so far, beside X25519.
A KEM (key encapsulation mechanism) replaces Diffie-Hellman: your public key wraps a fresh secret only you can unwrap. TLS runs ML-KEM beside X25519: an attacker must break both. SLH-DSA, built only from hash functions, is the cautious backup.
Lattices and LWE
Linear equations are easy to solve. Add a little noise to each and they become hard, as far as we know even for quantum computers.
Given exact equations a·s = b, elimination finds s at once. Add a small error to each, modulo q, and with hundreds of unknowns every known algorithm, classical or quantum, takes exponential time. ML-KEM and ML-DSA rest on this.
| a | e | b = a·s + e |
|---|---|---|
| ( 1, 6, 94) | +1 | 25 |
| (67, 50, 39) | -1 | 9 |
| (45, 23, 53) | +1 | 55 |
| (70, 25, 15) | 0 | 23 |
| (74, 50, 19) | 0 | 25 |
| (35, 28, 51) | +1 | 36 |
| (28, 94, 24) | +1 | 57 |
| (85, 18, 13) | 0 | 43 |
The secret is s = (15, 28, 53). Solving the first three equations as if they were exact gives (4, 38, 69): wrong, and nothing says by how much.
Decryption works for 510 of 510 possible encryptions.
Zero noise: plain linear algebra, broken. Small noise: hard for the attacker, harmless for the key holder. Too much: the errors add up past q/4 and decryption itself fails. Real schemes live in the middle, with hundreds of dimensions.
Zero-knowledge proofs
Convince someone that a statement is true, for instance that you know a secret, without revealing anything else.
Picture a ring-shaped cave whose two paths meet at a door only a magic word opens.
The prover has walked in, out of sight, by path A or B. You stand at the entrance and shout which path to come back by.
Complete: the honest prover always passes. Sound: a bluffer fails half the rounds. Zero-knowledge: the verifier learns nothing it could not have faked. Schnorr’s protocol, with numbers:
Hash t and a message to get c (Fiat-Shamir): the proof becomes a signature, as in Ed25519.
Secret sharing
Split a secret into n shares so that any k of them rebuild it, and k − 1 learn nothing at all.
Two points fix a line, three a parabola. To let any k of n trustees rebuild a key, hide it as f(0) of a random polynomial of degree k − 1; trustee i gets the point (i, f(i)).
Computing on encrypted data
Homomorphic encryption lets a server compute on ciphertexts and return an encrypted result it never saw in the clear.
In Paillier’s scheme, multiplying two ciphertexts adds the plaintexts; textbook RSA (chapter V) multiplies them.
Fully homomorphic schemes, built on lattices, allow any computation, at orders of magnitude the cost.
In one breath
- The quantum threat. Shor’s algorithm would break RSA, Diffie-Hellman and elliptic curves. Grover only halves symmetric strength, so AES-256 stays safe.
- Post-quantum standards. ML-KEM for key exchange, ML-DSA and SLH-DSA for signatures: NIST’s 2024 standards. Only ML-KEM is in wide use so far, beside X25519.
- Lattices and LWE. Linear equations are easy to solve. Add a little noise to each and they become hard, as far as we know even for quantum computers.
- Zero-knowledge proofs. Convince someone that a statement is true, for instance that you know a secret, without revealing anything else.
- Secret sharing. Split a secret into n shares so that any k of them rebuild it, and k − 1 learn nothing at all.
- Computing on encrypted data. Homomorphic encryption lets a server compute on ciphertexts and return an encrypted result it never saw in the clear.