0.7 Quantum computers and KEMs: why lattices

What a quantum computer is

An ordinary computer stores bits that are either 0 or 1. A quantum computer stores qubits, whose state is a combination of 0 and 1 described by complex numbers called amplitudes. Operations on qubits change all these amplitudes at once, and measuring gives one outcome with a probability set by them. This is not “trying every answer in parallel”: a measurement returns a single result. The trick is to arrange the computation so that wrong answers cancel and the right answer becomes likely. Only a few problems have that structure, and two of them matter for cryptography.

Today’s machines have a few hundred to a few thousand noisy qubits. Breaking real cryptography needs a fault-tolerant machine, which corrects its own errors and so needs far more physical qubits. No such machine exists yet. The question for engineers is not whether one exists today but whether data encrypted today still needs to be secret when one does.

Shor’s algorithm: public-key cryptography falls

In 1994 Peter Shor showed that a quantum computer can find the period of a function exponentially faster than any known classical method. Factoring a number $N$ and computing discrete logarithms both reduce to period finding. So a large quantum computer can:

• factor an RSA modulus and recover the private key (RSA encryption and RSA signatures);
• compute discrete logarithms modulo a prime (classic Diffie–Hellman, DSA);
• compute discrete logarithms on elliptic curves (ECDH, X25519, ECDSA, Ed25519).

These are exactly the problems behind public-key encryption and key exchange and digital signatures. Larger keys do not help: Shor’s running time grows only polynomially with the key size, so doubling an RSA key barely slows it down. The algorithms have to be replaced by ones built on different mathematics.

Grover’s algorithm: symmetric cryptography bends

Grover’s algorithm (1996) searches an unstructured space of $2^n$ possibilities in about $2^{n/2}$ steps instead of $2^n$. Applied to an AES key it looks like it halves the security level: AES-128 would drop to about 64 bits.

In practice the loss is much smaller. Each Grover step is a full AES evaluation built as a reversible quantum circuit, the steps must run one after another, and splitting the search across $K$ machines only shortens it by a factor of $\sqrt{K}$, not $K$. NIST still counts AES-128 as meeting its lowest post-quantum security category. The simple, conservative rule is still worth following: use AES-256 for data that must stay secret for a long time, and SHA-256 or SHA-384 for hashing. See symmetric encryption and hash functions for what these primitives do.

Harvest now, decrypt later

Why migrate before the machine exists? Because an adversary can record encrypted traffic today and keep it. If a TLS session’s key was agreed with ECDH, a future quantum computer can recover that key from the recorded handshake and decrypt everything in the session. Medical records, state secrets and long-lived business data may still matter in fifteen years.

Signatures are less urgent in this one respect: a forged signature only matters once someone can forge it, and old signatures can be re-issued. Key exchange protects data that has already been sent, so it goes first. That is why browsers and servers switched their key exchange to hybrid X25519MLKEM768 before touching certificates.

What a KEM is

Diffie–Hellman is symmetric in shape: both parties pick a secret, publish a value, and combine their own secret with the other’s public value. Post-quantum schemes do not have this neat structure, so the standards use a key encapsulation mechanism (KEM) instead.

Side by side, the two message flows look like this:

Diffie–Hellman                     KEM
Alice            Bob               Alice                   Bob
a (secret)       b (secret)                                 (ek, dk) = KeyGen()
A = g^a  ──A──►                                    ◄──ek──
         ◄──B──  B = g^b           (K, c) = Encaps(ek)
K = B^a          K = A^b                           ──c──►
                                                            K = Decaps(dk, c)

Both end with the same 32-byte secret, which then feeds a key derivation function and an authenticated cipher. The difference is who creates the secret: in Diffie–Hellman both sides contribute; in a KEM the sender generates it and wraps it for the receiver. For TLS the change is small: the client sends an encapsulation key where it used to send a DH share, and the server answers with a ciphertext.

Here is ML-KEM-768 in Python with the cryptography library (version 50):

from cryptography.hazmat.primitives.asymmetric.mlkem import MLKEM768PrivateKey
from cryptography.hazmat.primitives.serialization import Encoding, PublicFormat

# Bob: generate a key pair and publish the encapsulation key
bob_private = MLKEM768PrivateKey.generate()
bob_public = bob_private.public_key()
ek = bob_public.public_bytes(Encoding.Raw, PublicFormat.Raw)

# Alice: encapsulate -> (shared secret, ciphertext); she sends only the ciphertext
alice_secret, ciphertext = bob_public.encapsulate()

# Bob: decapsulate the ciphertext with his private key
bob_secret = bob_private.decapsulate(ciphertext)

print("encapsulation key:", len(ek), "bytes")
print("ciphertext:       ", len(ciphertext), "bytes")
print("shared secret:    ", len(alice_secret), "bytes")
print("secrets match:    ", alice_secret == bob_secret)

encapsulation key: 1184 bytes
ciphertext:        1088 bytes
shared secret:     32 bytes
secrets match:     True

The keys are random on every run, but the sizes and the match are always the same. Compare the sizes with X25519, where each side sends 32 bytes: post-quantum key exchange costs about a kilobyte more per handshake.

Hybrid key exchange

ML-KEM is new, and new algorithms sometimes have implementation bugs or, rarely, mathematical weaknesses. Deployments therefore run a classical and a post-quantum exchange together and derive the session key from both secrets. The result stays secure as long as either component holds. TLS 1.3 does this with the group X25519MLKEM768, now on by default in major browsers, OpenSSL 3.5 and Go. The hybrid TLS guide shows how to enable and check it.

The NIST standards

After an eight-year public competition, NIST has standardised or selected these algorithms:

HQC is a deliberate backup: if a weakness were found in ML-KEM, a KEM based on different mathematics would be ready. NIST still recommends ML-KEM for general use.

Deadlines

• NIST IR 8547 (initial public draft, November 2024) proposes that quantum-vulnerable public-key algorithms at the 112-bit level, such as RSA-2048 and P-256, be deprecated after 2030 and disallowed after 2035. Hybrid combinations with an approved post-quantum algorithm remain allowed.
• CNSA 2.0, the NSA’s suite for US national security systems, requires ML-KEM-1024 and ML-DSA-87, with some system types (software and firmware signing, networking equipment) switching well before the overall 2035 goal.

The PQC migration checklist turns these dates into concrete steps and 2.7 Post-quantum security explains the security levels.

Why lattices won

Three of the four NIST algorithms rest on lattice problems. The reasons are practical:

• Speed. ML-KEM key generation, encapsulation and decapsulation each take tens of microseconds, comparable to or faster than elliptic curves.
• Size. Keys and ciphertexts of about a kilobyte fit in a TLS handshake. Other families either have much larger keys (classic code-based schemes) or much larger signatures (hash-based ones).
• Confidence. The underlying problems, Learning With Errors and the shortest vector problem, have been studied since the 1980s and 1990s, and the best quantum attacks are not much better than the best classical ones.
• Versatility. The same mathematics gives key exchange, signatures and even computation on encrypted data (FHE).

What exactly is a lattice, and why is finding a short vector in one so hard? That is where the main part of this site begins: 1.1 What is a lattice?

Common mistakes

• Thinking larger RSA or ECC keys fix the problem. Shor’s algorithm scales polynomially; the fix is a different algorithm.
• Replacing AES because of quantum computers. AES and SHA-2 stay. Use 256-bit keys for long-lived secrets.
• Migrating signatures first. Recorded traffic is only exposed through its key exchange, so key exchange is the urgent part.
• Dropping the classical algorithm too early. Hybrid key exchange costs little and protects against a flaw in a young implementation.
• Treating a KEM as a drop-in Diffie–Hellman. The message flow differs: only the receiver has a key pair, and the sender’s output is a ciphertext.

Further reading

• NIST, FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard (2024).
• NIST, NIST selects HQC as fifth algorithm for post-quantum encryption (March 2025), and the NIST IR 8547 draft on the transition timeline.
• David Wong, Real-World Cryptography (Manning, 2021), chapter 14 on post-quantum cryptography (cited from memory).