Chapter 24 — The post-quantum algorithms

In one sentence

NIST has standardised a small set of quantum-resistant algorithms built on different hard problems — mainly structured lattices for the everyday ones, plus hash-based and code-based alternatives as hedges.

The NIST standards (finalised August 2024)

Standard	Name	Was called	Type	Replaces
FIPS 203	ML-KEM	CRYSTALS-Kyber	Key encapsulation (KEM)	ECDH / RSA key transport
FIPS 204	ML-DSA	CRYSTALS-Dilithium	Signature	ECDSA / RSA / EdDSA
FIPS 205	SLH-DSA	SPHINCS+	Signature (hash-based)	signatures where you distrust lattices
FIPS 206 (draft)	FN-DSA	Falcon	Signature (lattice, compact)	ECDSA where signature size matters

Plus, selected in 2025 as a backup KEM on different maths:

"ML" = Module-Lattice. "SLH" = StateLess Hash-based. "FN" = Fast Fourier over NTRU lattices.

The core idea: lattice problems

Most of the new standards rest on the difficulty of problems in lattices — a regular grid of points in high-dimensional space.

   Given a lattice (defined by some basis vectors) and a point that is
   NEAR a lattice point but not exactly on one:

     * SHORTEST VECTOR PROBLEM (SVP): find the shortest non-zero lattice vector
     * CLOSEST VECTOR PROBLEM (CVP): find the lattice point nearest the target
     * LEARNING WITH ERRORS (LWE):   solve linear equations that have small
                                     random "errors" added -- recovering the
                                     secret is as hard as lattice problems

   In 2 or 3 dimensions this is easy to eyeball. In 500+ dimensions with a
   "bad" basis, the best known algorithms -- classical OR quantum -- take
   exponential time. Crucially, Shor's period-finding does NOT apply.

ML-KEM and ML-DSA use a structured variant (Module-LWE) for efficiency. The structure is a mild theoretical risk (maybe it enables an attack nobody's found yet) — which is exactly why NIST also standardised hash-based SLH-DSA and selected code-based HQC. Different maths, so a break in one doesn't break the others.

ML-KEM (FIPS 203) — the key-exchange replacement

A KEM works slightly differently from Diffie–Hellman:

   DIFFIE-HELLMAN                    KEM (Key Encapsulation Mechanism)
   -------------                     --------------------------------
   both send a public value,        recipient publishes a public key.
   both derive the same secret      sender ENCAPSULATES: generates a random
                                    shared secret + a ciphertext that only
                                    the recipient's private key can open.
                                    Sender: (shared_secret, ciphertext)
                                    Recipient: decapsulate(ciphertext, sk)
                                               -> same shared_secret

Parameter sets (pick by security category; 768 is the recommended default):

Set	NIST level	Public key	Ciphertext	Shared secret	Rough classical equiv
ML-KEM-512	1	800 B	768 B	32 B	AES-128
ML-KEM-768	3	1184 B	1088 B	32 B	AES-192
ML-KEM-1024	5	1568 B	1568 B	32 B	AES-256

Compare: an X25519 public key is 32 bytes. ML-KEM-768's is 1184 — ~37x larger. That size growth, multiplied across every TLS handshake on earth, is the main cost of the transition. Still small in absolute terms, and speed is competitive with (often faster than) X25519.

ML-DSA (FIPS 204) — the default signature replacement

Set	NIST level	Public key	Signature	Notes
ML-DSA-44	2	1312 B	2420 B
ML-DSA-65	3	1952 B	3309 B	recommended default
ML-DSA-87	5	2592 B	4627 B	CNSA 2.0 mandates this level

Compare: Ed25519 is a 32-byte key and 64-byte signature. ML-DSA-65 is ~60x and ~50x bigger. For a TLS certificate chain (leaf + intermediate, each with a key and a signature), that's several extra kilobytes per handshake — enough to matter for QUIC's first flight and for constrained IoT.

SLH-DSA (FIPS 205) — the conservative signature

Built only from hash functions (Chapter 8–9). If SHA-2/SHA-3 are secure, SLH-DSA is secure — no lattice assumptions at all. The price:

   + Rock-solid security foundation (just needs a good hash)
   + Tiny public keys (32-64 bytes)
   + Stateless (unlike older hash-based schemes XMSS/LMS, which are
     catastrophic if you reuse state)
   - HUGE signatures: 7,856 bytes ("s" small variants) up to ~49,000 bytes
   - SLOW signing: milliseconds to tens of ms (100-1000x slower than ML-DSA)

   Use it for: firmware/boot signing, CA root signatures, code signing --
   things signed rarely, verified occasionally, and needing to stay valid
   for decades. NOT for per-connection TLS handshake signatures.

Naming: SLH-DSA-SHA2-128s = SHA-2, 128-bit security, small-signature (slow) variant; ...128f = fast-signing (bigger signature) variant.

FN-DSA / Falcon (FIPS 206, draft) — compact lattice signatures

Much smaller than ML-DSA (≈ 666-byte signature, 897-byte key at level 1), which is attractive for bandwidth-constrained protocols. But signing needs careful floating-point / Gaussian-sampling code that is very hard to make constant-time — a side-channel minefield. Still in draft. Wait for the standard and vetted implementations unless you have a specific, reviewed need.

HQC — the code-based backup KEM

Selected March 2025 as a second KEM standard, on error-correcting-code maths (decoding a random linear code is NP-hard) — completely different from lattices. Larger keys/ciphertexts than ML-KEM (public key ~2.2–7.2 KB depending on level). Its job is insurance: if a devastating attack on Module-LWE ever appears, HQC is ready. Standard expected 2026–2027.

The decision table

   NEED                         USE (2026)                    HEDGE / NOTES
   ----                         ----------                    -------------
   TLS / key exchange           HYBRID: X25519 + ML-KEM-768   (Chapter 25)
   General-purpose signature    ML-DSA-65                      or hybrid w/ Ed25519
   Firmware / boot / root CA    SLH-DSA (or LMS/XMSS if        conservative,
                                stateful mgmt is airtight)     hash-only
   Bandwidth-critical sig       wait for FN-DSA standard       ML-DSA meanwhile
   Backup KEM / crypto-agility  keep HQC on the roadmap        different maths
   Symmetric / hashing          AES-256, SHA-384+             no PQC needed

Practice (25 min)

Make a table for your main project: every place it uses RSA/ECDH/ECDSA/EdDSA, and next to each, the PQC replacement from the decision table and the size delta (bytes before → after).
Estimate the handshake-size impact: if a TLS cert chain adds one ML-DSA-65 key+signature at the leaf and one at the intermediate, how many extra bytes per handshake? (~2 × (1952 + 3309) ≈ 10.5 KB.) Would that break anything you run? (Check MTU-sensitive paths, QUIC initial limits, embedded flash sizes.)
Read the ML-KEM-768 parameters aloud until "1184-byte public key, 1088-byte ciphertext, 32-byte shared secret" is memorised. You'll cite these in design reviews.

Common confusions

"Post-quantum means it runs on a quantum computer." The opposite — it runs on ordinary computers and resists quantum attack.
"ML-KEM is a drop-in for ECDH." It's a KEM, not a DH. The API shape differs (encapsulate / decapsulate). Protocols need adapting, though TLS 1.3 already did.
"Just use SLH-DSA everywhere, it's the safest." Its signatures are kilobytes and signing is slow. Wrong tool for high-volume TLS.
"Lattice crypto is unproven." LWE has ~20 years of analysis and a worst-case-to-average-case reduction. The structured variants are newer; that's why hash-based and code-based hedges exist.
"We standardised these, so we're done." Migration — inventory, hybrid rollout, crypto-agility — is the hard part. Chapter 25.

Check yourself

Name the three finalised NIST PQC standards and what each is for.
What hard problem underlies ML-KEM and ML-DSA? Why doesn't Shor break it?
How does a KEM differ from Diffie–Hellman?
Give ML-KEM-768's public-key, ciphertext, and shared-secret sizes.
Why is SLH-DSA a poor fit for per-connection TLS signatures but a good fit for firmware signing?
Why did NIST standardise both lattice-based and hash/code-based algorithms?