Skip to content
Tutorials Center
My learning

Topics

Lesson 31 of 40 ยท Protocols and Practice

Post-Quantum Cryptography

Learn what quantum computers threaten, why Shor's algorithm breaks RSA and elliptic curves, and how lattice and hash-based schemes like ML-KEM answer it.

Almost everything in the public-key half of this course, RSA, Diffie-Hellman and elliptic curves, depends on two problems believed to be hard for ordinary computers: factoring large numbers and computing discrete logarithms. A large, error-corrected quantum computer would solve both in a reasonable time. Such a machine does not exist today, but cryptographers do not wait for it to exist, for reasons you will see below.

Post-quantum cryptography (PQC) means ordinary algorithms, running on ordinary computers, that are believed to resist attacks by quantum computers as well. It is not quantum cryptography; there is no quantum hardware in your phone. In 2024 the US standards body NIST published the first three PQC standards, and browsers and servers are already using them. This lesson explains the threat, the main families of replacement, and how to plan for the change.

What quantum computers change

Two quantum algorithms matter for cryptography.

Shor's algorithm (1994) finds the hidden period in certain mathematical functions exponentially faster than any known classical method. That one ability solves both integer factoring and discrete logarithms, including the elliptic-curve version. It breaks RSA, finite-field Diffie-Hellman, DSA and ECDSA/ECDH completely. Larger keys do not save them; making RSA bigger only makes the attack somewhat slower, not infeasible.

Grover's algorithm (1996) speeds up unstructured search: finding one needle among N possibilities takes about sqrt(N) steps instead of N. For cryptography that means a brute-force search of a k-bit key costs roughly 2^(k/2) quantum steps. This halves the security level of symmetric keys and hash preimages, which is a manageable problem: use longer keys.

flowchart TD
    Q["Large quantum computer"] --> SH["Shor's algorithm"]
    Q --> GR["Grover's algorithm"]
    SH --> B1["RSA, DH, DSA, ECDH, ECDSA<br/>broken"]
    GR --> B2["AES, SHA-2, SHA-3, HMAC<br/>security level halved"]
    B1 --> F1["Replace with post-quantum<br/>KEMs and signatures"]
    B2 --> F2["Use 256-bit keys and<br/>256-bit hashes"]

Shor's algorithm forces new public-key algorithms; Grover's only forces bigger symmetric parameters.

Shor's algorithm in three lines of classical code

Shor's algorithm turns factoring N into period finding. Pick a random a that shares no factor with N and look at the sequence a^x mod N. It repeats with some period r. If r is even and a^(r/2) is not -1 mod N, then gcd(a^(r/2) - 1, N) and gcd(a^(r/2) + 1, N) are factors of N.

Finding r is the hard part for a classical computer and the part a quantum computer does quickly. The example below does the quantum step the slow way (by trying exponents one by one), so it works only for tiny numbers, and shows that the rest of the method is simple arithmetic.

Python Factoring with period finding (classical stand-in for Shor)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

What Grover means for symmetric cryptography

Grover's speed-up is only quadratic, and it does not parallelize well, so a real attack on AES-128 would need an enormous quantum computer running for an extremely long time. The common conservative advice is still simple: halve the exponent and plan accordingly.

Python Security levels under Grover's algorithm

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Harvest now, decrypt later

Even if large quantum computers are years or decades away, an attacker can record encrypted traffic today and decrypt it once the technology exists. Anything that must stay secret for a long time (medical records, state secrets, long-lived trade secrets) is already at risk if it is protected only by RSA or elliptic-curve key exchange. That is why key exchange is being migrated first. Signatures are less urgent: forging a signature is only useful if it happens before the signature is checked, so there is no recorded archive to attack later. They still need replacing, because long-lived certificates, firmware roots and archives rely on them.

Hash-based signatures

The most conservative PQC idea needs nothing except a hash function, whose security Grover only halves. The simplest example is the Lamport one-time signature (1979).

  • Private key: for each of the 256 bits of the message hash, two random secrets, one for a 0 bit and one for a 1 bit (512 secrets).
  • Public key: the hash of every secret.
  • Signing: for each bit of the message hash, reveal the secret that matches the bit's value.
  • Verifying: hash each revealed secret and compare it with the public key entry for that bit and value.

A forger would have to invert the hash to produce a secret they have not seen. But the key may be used once: every signature reveals half of the secrets, and a second signature reveals more. Practical schemes, XMSS and the standardized SLH-DSA (formerly SPHINCS+), chain many one-time keys together in a Merkle tree so that one small public key (a tree root) covers thousands or even an effectively unlimited number of signatures.

Python A Lamport one-time signature, and why reuse is fatal

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With one or two signatures, no target is forgeable. A handful of reuses later, an attacker holds enough revealed secrets to sign messages of their choice. Real hash-based schemes therefore track state carefully (XMSS) or avoid state altogether at the cost of larger signatures (SLH-DSA).

Lattice-based cryptography

The workhorse of the new standards is lattice cryptography, built on the Learning With Errors (LWE) problem. Imagine a secret vector s and many random vectors a_i. You are shown the products b_i = <a_i, s> + e_i mod q, where each e_i is a small random error. Recovering s from these noisy equations is believed to be hard, even for quantum computers. Without the noise it would be easy: ordinary linear algebra, which is exactly how you will break the noiseless version below.

Encryption in the style of Regev's original 2005 scheme hides one bit: add up a random subset of the public equations, and add q/2 if the bit is 1. The owner of s subtracts <u, s>; what is left is a small number (the accumulated errors) for a 0 bit, or a number near q/2 for a 1 bit.

Python Toy LWE encryption, and why the noise matters

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Without noise the system is solved at once. With noise of just plus or minus one, the equations contradict each other and elimination returns garbage. Real parameters use hundreds of dimensions and structured (ring or module) versions of the problem, so keys and ciphertexts are compact enough to use.

The NIST standards

In August 2024 NIST published three final standards, with names that replaced the research names:

Standard Name Purpose Based on
FIPS 203 ML-KEM (from CRYSTALS-Kyber) Key encapsulation (key exchange) Module lattices
FIPS 204 ML-DSA (from CRYSTALS-Dilithium) Digital signatures Module lattices
FIPS 205 SLH-DSA (from SPHINCS+) Digital signatures Hashes only

A KEM (key encapsulation mechanism) is the post-quantum replacement for Diffie-Hellman. The receiver publishes a public key; the sender calls encapsulate, which outputs a random shared secret plus a ciphertext; the receiver calls decapsulate on the ciphertext to get the same secret. The API is three functions:

Python
# Pseudocode: the shape of every KEM, not a real library API
public_key, private_key = kem_keygen()
ciphertext, shared_secret_sender = kem_encapsulate(public_key)
shared_secret_receiver = kem_decapsulate(private_key, ciphertext)
# both shared secrets are 32 bytes and equal; feed them to HKDF as usual

The price of the new algorithms is size. Sizes in bytes:

Algorithm Public key Ciphertext / signature
X25519 (today) 32 32
ML-KEM-512 800 768
ML-KEM-768 1,184 1,088
ML-KEM-1024 1,568 1,568
Ed25519 signature 32 64
ML-DSA-44 1,312 2,420
ML-DSA-65 1,952 3,309
ML-DSA-87 2,592 4,627
SLH-DSA-128s 32 7,856

ML-KEM-768 is the common choice for key exchange. These sizes are why post-quantum certificates and signatures are a harder deployment problem than key exchange: a certificate chain contains several signatures and public keys.

Quantum cryptography: key distribution with BB84

Do not confuse post-quantum cryptography with quantum cryptography, which uses the physics of single photons to distribute keys. The best-known protocol is BB84 (Bennett and Brassard, 1984). Its security rests on the uncertainty principle: measuring a quantum state in the wrong way disturbs it, so an eavesdropper cannot copy the photons without leaving a trace.

How BB84 works:

  1. Alice sends a stream of photons, each encoding a random bit in one of two randomly chosen bases (say rectilinear or diagonal polarization).
  2. Bob measures each photon in a randomly chosen basis. When his basis matches Alice's, he reads her bit exactly. When it differs, his result is random.
  3. Over an ordinary public channel they announce which bases they used (never the bits) and keep only the positions where the bases matched. That is the sifted key, about half the length.
  4. They compare a random sample of the sifted key. If Eve measured photons in transit, she guessed the wrong basis about half the time, and each wrong guess corrupts Bob's result with probability one half. That gives an error rate near 25% in the sample, so Alice and Bob detect the intrusion and discard the key.

The entanglement-based variant E91 (Ekert, 1991) reaches the same goal using pairs of entangled photons and a test of Bell's inequality. A real system adds error correction and privacy amplification (hashing the key down) to remove the information Eve might still have.

The next program is a classical simulation of the protocol's statistics. It does not use any quantum hardware, but it reproduces the error rates that give an eavesdropper away.

Python Simulating BB84 with and without an eavesdropper

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Without Eve the error rate is zero (a real channel has some noise, so a small threshold is allowed). With Eve it is about 25%, which is impossible to miss. Limits: QKD needs special fibre or satellite links, works over limited distances without trusted relays, and only protects key exchange. It does not authenticate the parties, so it still needs a pre-shared secret or signatures. Governments such as the NSA and the UK NCSC therefore prefer the software route of post-quantum algorithms for most uses.

Migrating

Nobody trusts a young algorithm alone, so deployments combine old and new. Hybrid key exchange runs X25519 and ML-KEM together and mixes both secrets with a KDF; an attacker must break both. Browsers and large providers already use a hybrid group of this kind in TLS. Practical steps for an organization:

  1. Inventory where public-key cryptography is used: TLS, VPNs, code signing, stored encrypted archives, hardware devices, third-party software.
  2. Prioritize data with a long secrecy lifetime, because of harvest-now-decrypt-later.
  3. Build crypto-agility: algorithms should be configuration and negotiation, not hard-coded constants, so they can be swapped in months rather than years.
  4. Prefer libraries and protocols that already support PQC; do not implement it yourself.
  5. Follow national guidance and timelines. NIST's draft transition plan proposes deprecating RSA and elliptic-curve algorithms by 2030 and disallowing them by 2035.

A few caveats: newer algorithms have had less scrutiny (a well-known candidate, SIKE, was broken by a classical attack in 2022, after reaching the final selection rounds), implementations need side-channel care, and symmetric cryptography needs only 256-bit keys and hashes, not a redesign.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which problem does Shor's algorithm make easy?

    Shor's algorithm finds periods efficiently, which solves factoring and discrete logarithms, the problems behind RSA, Diffie-Hellman and elliptic-curve cryptography.
  2. 2. What is the practical response to Grover's algorithm?

    Grover gives a quadratic speed-up, so a 256-bit key still leaves about 128 bits of security. Public-key schemes broken by Shor need replacement, not just bigger sizes.
  3. 3. Why are key exchanges migrated to PQC before signatures?

    That is harvest now, decrypt later: encrypted data captured today can be broken in the future, so protecting its key exchange is urgent.
  4. 4. What is the main limitation of a Lamport signature key?

    Every signature reveals one secret per hash bit. After a few signatures an attacker holds enough secrets to sign other messages, so a key is single-use.
  5. 5. What does hybrid key exchange do?

    Both shared secrets are fed into the key derivation. The result is secure as long as either algorithm holds, which hedges against flaws in the newer one.

Summary

  • Shor's algorithm would break RSA, finite-field Diffie-Hellman and elliptic-curve cryptography; Grover's only halves the security level of symmetric keys and hashes, so 256-bit parameters remain fine.
  • Harvest-now-decrypt-later makes key exchange the first thing to migrate.
  • Hash-based signatures (Lamport, XMSS, SLH-DSA) rely only on hash security; one-time keys must never be reused.
  • Lattice schemes rest on Learning With Errors: noisy linear equations that are hard to solve. NIST standardized ML-KEM (FIPS 203), ML-DSA (FIPS 204) and SLH-DSA (FIPS 205) in 2024.
  • Post-quantum keys and signatures are bigger. Use hybrid key exchange, inventory your cryptography, aim for crypto-agility and rely on reviewed libraries.

Next: Steganography, hiding the very existence of a message. After that, the Encrypted Vault project combines key derivation, encryption and authentication into one small application.