Post-quantum cryptography

Almost all the public-key cryptography in use today, including the key exchanges and certificates from earlier lessons, would fall to a large enough quantum computer. Nobody has built one yet. But the replacement is already standardised and rolling out, and there are good reasons it couldn't wait.

What quantum computers change

A quantum computer isn't simply a faster computer. For most tasks it offers no advantage at all. But for a few specific mathematical problems, quantum algorithms are dramatically faster than anything a normal computer can do. Unfortunately, two of those problems are exactly the ones public-key cryptography relies on.

• Shor's algorithm (1994) factors large numbers and solves discrete logarithms efficiently. That breaks RSA, Diffie–Hellman, elliptic-curve Diffie–Hellman, ECDSA and Ed25519, all at once. Making keys bigger doesn't help; Shor's algorithm scales too well.
• Grover's algorithm (1996) speeds up brute-force search, but only by a square root. Searching 2¹²⁸ keys takes about 2⁶⁴ quantum steps instead. That weakens symmetric ciphers and hash functions without breaking them, and doubling the key size cancels it out.

The rest of a secure connection, the AES encryption and the hashing, is fine. What's at risk is the public-key part: how two parties agree on keys, and how they prove who they are.

Should you worry yet?

If quantum computers don't exist yet, why act now? Because of a strategy called harvest now, decrypt later. An attacker can record encrypted traffic today and store it until a quantum computer can break the key exchange. Anything still secret by then gets exposed: medical records, state secrets, long-term business plans.

In 2015, Michele Mosca put the decision into one inequality. Let x be how many years your data must stay secret, y how many years it will take you to migrate to quantum-safe cryptography, and z how many years until a cryptographically relevant quantum computer exists. If x + y > z, you're already too late for some of your data.

Nobody knows z. Expert surveys spread their estimates over a decade or more, and some think it may never happen at useful scale. But for data that must stay secret for 20 years, even a cautious estimate makes x + y > z uncomfortably likely. That's why governments and large companies began migrating years before any quantum computer could threaten them.

Hiding secrets in noise

The replacements rest on mathematical problems that no known quantum algorithm solves efficiently. The most important family is based on lattices, and in particular a problem called learning with errors (LWE), introduced by Oded Regev in 2005.

Start with something easy. If I give you a set of equations like these, with all arithmetic modulo 97, you can find the secret numbers s₁ to s₄ with school algebra:

23·s₁ + 71·s₂ +  5·s₃ + 88·s₄ = 40
61·s₁ +  9·s₂ + 44·s₃ + 12·s₄ = 17
 …

Now add a small random error to the right-hand side of each equation: +2 here, −1 there. The equations become almost true. That tiny change ruins the algebra: errors pile up with every step, and the answer comes out as nonsense. With hundreds of secret numbers instead of four, nobody knows how to recover the secret, with either a classical or a quantum computer.

The trick is that someone who knows the secret can still use the noisy equations. Encryption hides each bit in a sum of equations, offset by half the modulus for a 1. The legitimate receiver subtracts what the secret predicts, leaving a value near 0 for a 0, or near 48 for a 1, plus some leftover noise. As long as the noise stays small, rounding recovers the bit.

Set the noise to 0 and the scheme still works, but then it's just ordinary equations, which anyone can solve. Push it to 6 and about one message in seven comes back with a flipped bit; at 8, about half do. Real designs like ML-KEM choose their sizes so that noise hides the secret while decryption failures are vanishingly rare, about 1 in 2¹⁶⁴ for ML-KEM-768.

The new standards

In 2016, the US National Institute of Standards and Technology (NIST) opened a public competition for quantum-resistant algorithms. Eight years and several rounds of public attack later, in August 2024, it published the first three standards:

A fourth, FN-DSA, based on the Falcon signature scheme, is on its way. In 2025 NIST also picked HQC, built on error-correcting codes, as a backup to ML-KEM, so that not everything depends on lattices.

The price: size

Post-quantum algorithms are fast, often faster than RSA. Their cost is size. Keys, ciphertexts and signatures are tens to hundreds of times larger than the elliptic-curve versions they replace, which matters when they have to fit into network packets, smart cards and certificate chains.

Signatures from nothing but hashes

SLH-DSA is the most conservative of the new standards because it needs no new mathematics at all. Its security rests only on hash functions like SHA-256, which quantum computers barely dent. Its ancestor is a scheme Leslie Lamport described in 1979, simple enough to build in a few lines.

1. Make a key For each bit of a message's hash, generate two random secrets: one for “0” and one for “1”. The private key is all the secrets. The public key is the hash of each one.
2. Sign Hash the message. For each bit, reveal the secret that matches it. That set of secrets is the signature.
3. Verify Hash the message the same way. For each bit, hash the revealed secret and check it matches the right half of the public key.

Sign a second, different message with the same key and look at the red columns. Wherever the two messages' hashes differ, both secrets of a pair are now public, so anyone could mix and match them to sign new messages. That's why each Lamport key can only be used once. SLH-DSA solves this by organising thousands of one-time keys into a giant tree of hashes, so one public key can safely sign many messages. The cost is signatures of 8 to 50 kilobytes.

Hybrid: belt and braces

The new algorithms have had far less scrutiny than elliptic curves, and SIKE showed that a respected scheme can fall overnight. So the first deployments don't replace classical cryptography. They run both side by side.

1. Send both key shares Your browser's first message includes an X25519 public key, as in the ECDHE lesson, and an ML-KEM-768 public key.
2. Get both back The server replies with its X25519 share and an ML-KEM ciphertext.
3. Combine the secrets Both shared secrets go into the key derivation function together. An attacker would need to break X25519 and ML-KEM to recover the session keys.

This combination, called X25519MLKEM768, is already the default in Chrome, Firefox and Cloudflare. Signal added post-quantum protection to its key agreement in 2023, and Apple's iMessage followed in 2024. If you're reading this in a current browser, there's a good chance this page arrived over a quantum-resistant connection.

Signatures are harder. Certificate chains carry several signatures and public keys, and switching them all to ML-DSA would add kilobytes to every connection. That migration is still being worked out.

Planning the switch

For an organisation, post-quantum migration is less about mathematics and more about knowing what you have. NIST has proposed retiring today's quantum-vulnerable public-key algorithms by 2030 and disallowing them by 2035.

1. Inventory your cryptography Find every place that uses public-key cryptography: TLS, VPNs, SSH, code signing, document signing, hardware tokens, and the libraries and vendors behind them.
2. Prioritise by lifetime Apply Mosca's inequality. Data that must stay secret for decades, and devices that will be in the field for decades, come first.
3. Move key exchange to hybrid This protects against harvest-now-decrypt-later, and in many cases it's a library upgrade or configuration change.
4. Build crypto agility Design systems so algorithms can be swapped through configuration instead of rewrites. This migration won't be the last.
5. Test for size Larger keys have broken real systems: some network equipment dropped TLS handshakes that no longer fit in one packet. Test before you roll out.

Why this matters

• Quantum computers threaten public-key cryptography, not everything. Shor's algorithm breaks RSA and elliptic curves. Symmetric encryption and hashes just need large enough keys.
• The threat starts before the computer exists. Harvested traffic can be decrypted later, so long-lived secrets need protecting now.
• Noise is the new hard problem. Lattice schemes like ML-KEM hide secrets in nearly-true equations that neither kind of computer knows how to untangle.
• The switch is already happening. Hybrid key exchange is on by default in major browsers. Signatures, certificates and long-lived devices are next.