post-quantum cryptography

A large enough quantum computer would break the public key crypto that protects almost everything today. Post-quantum cryptography (PQC) is the set of new algorithms designed to survive it, and the migration has already started.

what breaks

Shor's algorithm solves the maths behind RSA and elliptic curves efficiently on a quantum computer. Grover's algorithm speeds up brute force, but only by a square root, so symmetric crypto just needs big enough keys.

algorithm         used for          quantum impact
rsa               encrypt, sign     broken by shor
ecdh, x25519      key exchange      broken by shor
ecdsa, ed25519    signatures        broken by shor
aes-128           symmetric         weakened by grover
aes-256           symmetric         fine
sha-256, sha-3    hashing           fine

why it matters now

Nobody has a quantum computer that can do this yet. But encrypted traffic can be recorded today and decrypted once one exists. Anything that must stay secret for ten years or more is already exposed.

        today                         later
          |                             |
          v                             v
+-----------------------+     +-----------------------+
| record encrypted      | --> | decrypt it with a     |
| traffic, store it     |     | quantum computer      |
+-----------------------+     +-----------------------+

           "harvest now, decrypt later"

Signatures are less urgent, because forging one needs the quantum computer at the time. But anything signed to last, like root certificates and firmware, needs a long lead time.

the new standards

NIST published the first PQC standards in August 2024. They rely on maths problems with no known quantum shortcut, mostly lattices and hashes.

standard    name       type           based on
fips 203    ml-kem     key exchange   lattices   (was kyber)
fips 204    ml-dsa     signatures     lattices   (was dilithium)
fips 205    slh-dsa    signatures     hashes     (was sphincs+)

FN-DSA (Falcon), and HQC, a backup key exchange built on different maths, are on the way.

the cost is size

                 public key    ciphertext or signature
x25519           32 b          32 b
ml-kem-768       1,184 b       1,088 b

ed25519          32 b          64 b
ml-dsa-65        1,952 b       3,309 b
slh-dsa-128s     32 b          7,856 b

The new algorithms are fast, but big. Bigger keys and signatures mean bigger handshakes, heavier certificate chains and more bytes on every connection.

hybrid for now

The new algorithms are young, so the safe choice is to combine a classical algorithm with a post-quantum one. An attacker then has to break both.

x25519  -->  secret a  --.
                         +-->  kdf(a, b)  -->  session key
ml-kem  -->  secret b  --'

This is already the default across much of the internet. Major browsers and CDNs use X25519MLKEM768 for TLS, and OpenSSH 10 defaults to mlkem768x25519-sha256.

getting ready

  1. find where you use rsa and ecc: tls, ssh, vpns, code signing, pki, hsms
  2. start with data that has to stay secret for years
  3. build crypto agility: make algorithms configurable, not hard coded
  4. turn on hybrid key exchange wherever it is available
  5. plan for larger keys and signatures in pki and firmware