One Event, Three Assumptions, Five Answers: A Field Guide to the Post-Quantum Toolkit

1. Somebody Is Already Saving Your Handshake#

Right now, somewhere, a machine may be recording this very TLS session -- not to read today, but to decrypt on the afternoon a large quantum computer finally boots. That is not a thriller premise. It is the stated design assumption behind a change that is already shipping in production TLS software, where the default key exchange offered is no longer plain X25519 but a hybrid whose second half is called ML-KEM ^[11]. The strange part is not that the field replaced the math. It is that replacing it took five different algorithms, resting on three unrelated hard problems, to answer a single result published in 1994 -- and that, so far, not one of the five has actually been broken.

The single result is Shor's algorithm. In 1994 Peter Shor showed that a large, fault-tolerant quantum computer could factor integers and compute discrete logarithms in polynomial time ^[1]. That one capability condemns essentially every public-key system deployed on the internet: RSA rests on factoring, Diffie-Hellman and elliptic-curve cryptography rest on discrete logarithms. (This series covered those primitives directly in Part 14 on RSA, Part 15 on elliptic curves, and Part 18 on Diffie-Hellman.) The moment a cryptographically relevant quantum computer exists, all three fall together.

Harvest now, decrypt later is why this is urgent before any quantum computer exists. If your threat model includes an adversary who can afford disk space and patience, then a session key protecting a 20-year secret is already at risk today ^[12]. That is the reasoning behind migrating key establishment first, and it is why the hybrid X25519MLKEM768 key share now ships as a default key share in OpenSSL 3.5, and was enabled by default in OpenSSH 9.9 before becoming the default key exchange in OpenSSH 10.0 ^{[11] [13] [14]}.

So the threat is one thing, sharp and singular. Why is the answer five things? NIST did not standardize one post-quantum cipher; it assembled a toolkit -- three finalized standards and two more in progress -- and spread it across three unrelated families of hard problem: structured lattices, hash functions, and error-correcting codes. The bet is that a mathematical breakthrough against one family is unlikely to touch the others. To see why the answer is a toolkit, not a single cipher: its parts are older than the threat they answer.

2. The Threat, and the Three Old Ideas That Outlived It#

Here is the twist that makes the whole story make sense: the replacements predate the threat. The oldest members of the toolkit were invented for reasons that had nothing to do with quantum computers, and they turned out to be quantum-safe by accident.

Robert McEliece published a code-based public-key cryptosystem in 1978, hiding a secret, efficiently decodable error-correcting code (a binary Goppa code) behind a scrambled generator matrix so that an attacker faces the task of decoding a random-looking linear code ^[15]. One year later, Ralph Merkle showed how to build digital signatures out of nothing but a hash function, chaining one-time keys under a binary hash tree whose root is the public key ^[16]; he polished the construction a decade later as "A Certified Digital Signature" ^[17]. Both predate Shor by fifteen-plus years. Both are still standing.

Then, in 1994, the threat arrived. Shor's quantum algorithm solves factoring and discrete logarithm in polynomial time, condemning RSA, Diffie-Hellman, and elliptic curves the moment a large quantum computer runs it ^[1]. Two years later Lov Grover found a quantum search algorithm with a quadratic speedup ^[18]. Grover is the good news that bounds the damage: a mere square-root speedup means doubling a symmetric key or hash-output length restores the security margin, which is exactly why hash-based signatures are considered the most conservative branch of the toolkit. Shor is catastrophic (exponential to polynomial); Grover is survivable (a square-root factor). The asymmetry is the reason symmetric ciphers and hash functions merely need bigger parameters, while public-key cryptography needed entirely new hard problems.

Lattices arrived on a separate track, and again for their own reasons. In 1996 Miklos Ajtai proved a startling worst-case-to-average-case reduction: breaking a random instance of a certain lattice problem is as hard as breaking the worst case ^[19]. That single result promoted lattices from a curiosity to a rigorous foundation. In 1998 Hoffstein, Pipher, and Silverman published NTRU, the first lattice scheme compact and fast enough to consider deploying, working over a small polynomial ring with tiny coefficients ^[20]. NTRU was first announced at the CRYPTO 1996 rump session but formally published at ANTS-III in 1998, so you will see both dates in the literature. Merkle's hash-tree work has the same two-date character: the 1979 thesis, then the 1989 CRYPTO paper.

Oded Regev tied the knot in 2005 with Learning With Errors (LWE), a versatile assumption whose hardness reduces (quantumly) to worst-case lattice problems and whose one-sentence intuition -- add noise to linear algebra -- runs through every lattice member of the toolkit ^[21].

The last pieces are the mechanisms that make these foundations into safe schemes. The Fujisaki-Okamoto transform (1999) upgrades a weak encryption scheme into a strong one by re-encrypting on decryption and checking consistency ^[22]. The GPV framework (2008) showed how to build lattice hash-and-sign signatures using a trapdoor and discrete-Gaussian sampling ^[23]. Lyubashevsky's "Fiat-Shamir with aborts" (2009) offered a rival way to sign, rejecting and restarting whenever a candidate would leak the key ^[24]. Ring-LWE (2010) moved LWE into polynomial rings for compact keys and fast arithmetic ^[25]. And in 2015, SPHINCS made hash-based signatures stateless, removing the operational footgun that had kept Merkle's idea out of ordinary hands ^[26].

timeline
title Post-quantum foundations predate the 1994 threat
1978 : McEliece code-based encryption
1979 : Merkle hash-based signatures
1994 : Shor algorithm breaks RSA and ECC
1996 : Grover search : Ajtai hard lattices
1998 : NTRU ring lattices
2005 : Regev Learning With Errors
2008 : GPV lattice hash-and-sign
2009 : Fiat-Shamir with aborts
2010 : Ring-LWE efficiency
2015 : SPHINCS stateless hashing

Read the timeline as three columns hiding in one line. Codes and hashes (1978, 1979) are the ancient, conservative branches. Lattices (1996 to 2010) are the young, efficient branch that took the most theoretical work to make safe. The mechanisms (FO, GPV, Fiat-Shamir-with-aborts) are the connective tissue that turns a hard problem into a usable cipher.

Each of these old ideas was quantum-safe. And none was deployable as written. To see why, watch each one walk straight into a different wall.

3. Three Walls: Why the Old Ideas Could Not Ship#

A cipher can be perfectly correct -- decrypting every honest message, verifying every honest signature -- and still be unusable, or worse, still hand over its secret key. The first generation of post-quantum schemes taught that lesson three times, each on a different axis.

The first wall is size. McEliece's cryptosystem has resisted cryptanalysis for more than forty-five years, which is a stronger track record than RSA has. But its public key is an entire generator matrix. In the modern Classic McEliece parameter sets, that means a public key from roughly 261 KB (for the mceliece348864 set) up to about 1.36 MB (for mceliece8192128) ^[27]. A megabyte of key material per connection is a non-starter for a TLS handshake that budgets a few kilobytes. McEliece is not broken; it is simply too big to carry. Its security was never the problem. Its shape was.

The second wall is state. Merkle's hash-tree signatures, engineered into the modern XMSS and LMS schemes and standardized by NIST in SP 800-208, are compact and rest on the most conservative assumption in cryptography ^[28]. But they are stateful: the signer must advance a one-time-key index after every signature and must never, ever reuse one.

The third wall is the subtle one, and it reframes the whole problem: leakage. The natural way to sign with a lattice is hash-and-sign in the style of GGH and its NTRU instantiation, NTRUSign: hash the message to a target point, then use your secret "good" basis to round to a nearby lattice point. A verifier checks the point is on the lattice and close to the target. It verifies perfectly. It is also fatally broken.

In 2006, Phong Nguyen and Oded Regev showed why in a paper with a wonderful title: "Learning a Parallelepiped" ^[29]. Every signature is the difference between the hashed target and a lattice point, and those differences are distributed over the fundamental parallelepiped of the secret basis. Collect a few hundred signatures, and you can reconstruct the shape of that parallelepiped -- which is to say, you can recover the secret key. The signer was leaking the key a little at a time, in the statistical shape of its own outputs, while every individual signature passed verification.

Put the three walls side by side and a pattern appears. McEliece fails on size, stateful hashes fail on operational state, and NTRUSign fails on leakage -- three completely different axes. The naive strategy of "pick the oldest unbroken idea and ship it" runs aground because being unbroken is not the same as being safe to deploy. The NTRUSign failure is the sharpest version of the lesson, because it severs two ideas most people treat as one.

Correctness is not security. A scheme can verify every honest signature and still surrender its secret key through the statistical shape of a few hundred outputs. The real design goal is not "find math no one has broken." It is "make the outputs reveal nothing about the secret."

That reframing is the hinge of the entire toolkit. Once you decide the enemy is any correlation between your public outputs and your private key, the design problem becomes concrete: engineer the transcript, the ciphertext, and the failure behavior so they are provably independent of the secret. That single idea, applied four different ways, is the modern toolkit.

4. The Competition: One Fix, Four Times#

The forcing function was not a single genius. It was an open, adversarial competition. NIST issued its public Call for Proposals in December 2016 and spent the next years pruning dozens of submissions across multiple rounds, documenting the reasoning in status reports as it went ^[30]. What emerged was not one lineage but four convergent tracks, running inside three unrelated hardness assumptions, each track advancing by fixing the specific flaw that sank its predecessor.

flowchart LR
subgraph TA["Track A -- codes"]
A1[McEliece 1978] --> A2[Niederreiter] --> A3[QC-MDPC BIKE] --> A4[HQC]
end
subgraph TB["Track B -- hashes"]
B1[Lamport OTS] --> B2[Merkle WOTS] --> B3[XMSS LMS] --> B4[SPHINCS+]
end
subgraph TC["Track C -- lattice KEM"]
C1[NTRU] --> C2[LWE] --> C3[Ring-LWE] --> C4[Module-LWE]
end
subgraph TD["Track D -- lattice signatures"]
D1[GGH NTRUSign] --> D2[GPV Falcon]
D1 --> D3[Fiat-Shamir Dilithium]
end
A4 --> TK[Five toolkit tips]
B4 --> TK
C4 --> TK
D2 --> TK
D3 --> TK
P1[SIKE isogeny] -.broke 2022.-> XX[Pruned families]
P2[Rainbow multivariate] -.broke 2022.-> XX

Track A, codes, is a war on key size. McEliece's matrix is enormous, so Niederreiter published the "dual" version that sends a compact syndrome instead of a full codeword -- smaller ciphertext, but the public key is still a matrix. Quasi-cyclic MDPC codes then collapsed that key to a few kilobytes by making the matrix reconstructable from a single row, an idea realized in the BIKE scheme ^[31].

But BIKE walked into a wall of its own. Its iterative bit-flipping decoder occasionally fails, and -- this is the trap -- those failures depend on the secret key. In 2016 Guo, Johansson, and Stankovski turned that into a full reaction attack: feed the decoder crafted ciphertexts, watch which ones fail, and recover the private key from the pattern of failures ^[32]. The very feature that shrank the key opened a side channel.

HQC is the fix: keep the quasi-cyclic key size, but decode with a public, fixed code whose failure rate can be bounded analytically and does not depend on the secret. That is precisely why NIST chose HQC over BIKE -- its DFR analysis was judged more mature ^[6].

Track B, hashes, is a war on state, and the whole story is the fight against one number: the leaf index. Lamport's one-time signature signs once per key; Merkle put many one-time keys under a tree so one root signs many messages; XMSS and LMS engineered that into standardized, stateful schemes ^[28]; and SPHINCS removed the state entirely by choosing a random leaf from a space so vast that collisions are negligible, backed by a few-time signature to absorb the rare clash ^[26]. SPHINCS+ then hardened it with tweakable hashes and a tighter few-time scheme called FORS ^[33].

Track C, lattice KEMs, is a war over structure. NTRU was fast but rested on a heuristic assumption; LWE bought a worst-case hardness reduction but needed a full random matrix as its key; Ring-LWE compressed that matrix to a single polynomial with fast NTT arithmetic ^[25]; and Module-LWE dialed the ring structure partway back down, trading a sliver of efficiency for a hedge against the possibility that too much algebraic structure helps the attacker ^[34].

Track D, lattice signatures, is where the tree forks and both branches survive. The GGH/NTRUSign transcript leak forced a choice, and the field kept two answers: GPV hash-and-sign, which samples from a discrete Gaussian whose shape is provably independent of the secret basis (this becomes Falcon), and Fiat-Shamir with aborts, which rejects and restarts until the transcript is key-independent (this becomes Dilithium) ^{[23] [24]}.

Stare at those four tracks and the same move appears in every one.

Every surviving generation makes the transcript or the failure channel provably independent of the secret. Gaussian sampling and rejection sampling remove the signature-transcript leak; the Fujisaki-Okamoto transform removes the decryption-failure oracle; statelessness removes the operational-state leak; HQC's public decoder removes BIKE's secret-dependent failures. The toolkit is not five unrelated tricks. It is one principle instantiated five ways.

The competition also pruned in public, and the prunings are the best argument for the whole strategy.

This is the moment to state the honest ending up front -- the argument the rest of the article defends.

Nothing in the toolkit has been mathematically broken. Every real-world failure so far has been an implementation leak -- and the two famous algorithmic breaks of the era hit schemes that never made the cut.

It helps to see every notable failure of the era in one place, sorted by what actually went wrong. Two of these are implementation leaks in surviving schemes (the math is intact); two are historical breaks of superseded designs; and two are the non-toolkit cryptanalytic breaks that justify the hedge.

Notice that the bottom two rows -- the only failures inside the toolkit -- are both in the "implementation" column, never the "math" column. That distinction is the spine of everything that follows. By 2024 the pruned tree had five surviving tips. Three of them became law on a single day.

5. Three Standards in One Day#

On 2024-08-13, NIST published three Federal Information Processing Standards at once: FIPS 203 (ML-KEM) for key encapsulation, FIPS 204 (ML-DSA) and FIPS 205 (SLH-DSA) for signatures ^{[2] [3] [4]}. That single date is when post-quantum cryptography crossed from an open competition into the law of the land, the thing an auditor can require and a protocol can mandate.

Each standard is the hardened descendant of a competition submission, and each carries one defining idea forward.

ML-KEM is Module-LWE encryption wrapped in a Fujisaki-Okamoto transform with implicit rejection, so that an invalid ciphertext yields a pseudo-random shared secret rather than an error -- there is no decapsulation-failure oracle to probe ^[2]. ML-DSA is a Fiat-Shamir-with-aborts signature built entirely from uniform integers, chosen deliberately so the implementation needs no floating point and is easy to make constant-time ^[3]. SLH-DSA is a stateless hash-based signature whose security rests on nothing but its hash function -- the conservative backstop ^[4].

Two things follow that people routinely get wrong. First, the renaming is not a redesign: "Kyber" and "ML-KEM" are essentially the same scheme ^[34]. Second, the toolkit is not finished -- only three of the five are standardized, and the fourth and fifth are genuinely pre-final.

The migration is already underway on the finalized three. But a standard is a promise about an interface, not a proof of security. To defend a design in a review, you need what is under each name: the math, the exact sizes, and the specific way each one can still fail.

6. The Five Primitives in Depth#

One workhorse, one default, one backstop, one compact hopeful, one insurance policy. That is the toolkit in five phrases: ML-KEM is the workhorse KEM, ML-DSA the default signature, SLH-DSA the conservative backstop, FN-DSA the compact hopeful, and HQC the non-lattice insurance policy. Three of the five are lattice schemes, so learn the lattice intuition once and reuse it three times.

All byte sizes below are exact for the finalized three and explicitly pre-final for FN-DSA and HQC. Cycle counts come from the pqm4 Cortex-M4 benchmark harness unless labeled otherwise ^[35]. Never compare a Cortex-M4 cycle count against an AVX2 desktop number directly -- they are different machines. HQC's own figures are measured on an Intel i7-11850H and Falcon's on an Intel i5-8259U, so those live on a different scale than the M4 numbers used for cross-scheme comparison.

6.1 ML-KEM (FIPS 203): the workhorse#

ML-KEM is the standardization of CRYSTALS-Kyber, finalized as FIPS 203, and it is the only post-quantum primitive deployed at scale today ^{[2] [34]}. Its security rests on Module-LWE over the ring $R_q = \mathbb{Z}_q[X]/(X^{256}+1)$ with modulus $q = 3329$; the module rank $k \in \{2,3,4\}$ selects ML-KEM-512, ML-KEM-768, and ML-KEM-1024.

The scheme has two layers. The inner layer is an IND-CPA encryption scheme over the ring. The outer layer upgrades it to a CCA-secure KEM using the Fujisaki-Okamoto transform.

sequenceDiagram
participant S as Sender
participant R as Receiver
R->>S: public encapsulation key ek
Note over S: pick random m, derive shared key K and coins r
S->>R: ciphertext c that encapsulates m
Note over R: decrypt c to m-prime, re-derive K-prime and r-prime
Note over R: re-encrypt m-prime to c-prime and compare
alt c-prime equals c
Note over R: return true shared secret K-prime
else mismatch
Note over R: return pseudo-random key from secret z, no error
end

That implicit-rejection branch is the load-bearing idea. It is worth seeing in code just how little a tampered ciphertext reveals.

// Illustrative only -- NOT production crypto.
// ML-KEM decapsulation never reports "invalid". On a re-encryption mismatch it
// returns a pseudo-random key derived from a per-key secret z, so a tampered
// ciphertext produces a well-formed but useless key -- no distinguishable signal.

function toyHash(s) {
let h = 2166136261 >>> 0;
for (const c of String(s)) h = Math.imul(h ^ c.charCodeAt(0), 16777619) >>> 0;
return (h >>> 0).toString(16).padStart(8, '0');
}

const z = 'per-key-secret-z'; // implicit-rejection secret, never leaves the device

// Receiver decrypts c to m', re-encrypts m', and compares the result to c.
function decapsulate(c, mDecrypted, cReencrypted) {
if (cReencrypted === c) {
  return toyHash('real-shared-secret:' + mDecrypted); // the genuine key
}
return toyHash(z + ':' + c);                           // pseudo-random reject key
}

// Honest ciphertext: re-encryption matches, real key returned.
console.log('honest   :', decapsulate('c123', 'm', 'c123'));
// Tampered ciphertext: mismatch -> still a key, still no error.
console.log('tampered :', decapsulate('c999', 'm-garbled', 'c123'));
// The reject key is deterministic per (z, c) and looks like any other key,
// so the attacker cannot tell rejection from success. The oracle is closed.

The exact bytes are what a protocol actually carries. For ML-KEM the encapsulation key / decapsulation key / ciphertext / shared secret sizes are 800 / 1632 / 768 / 32 for ML-KEM-512, 1184 / 2400 / 1088 / 32 for ML-KEM-768, and 1568 / 3168 / 1568 / 32 for ML-KEM-1024 ^[2]. The decryption-failure rates are $2^{-138.8}$, $2^{-164.8}$, and $2^{-174.8}$ respectively -- negligible by design, which as we saw is a security requirement, not a mere nicety ^[2]. On Cortex-M4, ML-KEM-768 costs roughly 642k / 659k / 708k cycles for keygen / encapsulate / decapsulate ^[35].

ML-KEM excels because it is small, fast, and easy to implement over small integers mod a fixed prime. It is the default post-quantum KEM in shipping software: the X25519MLKEM768 hybrid is a default key share in OpenSSL 3.5, and it was enabled by default in OpenSSH 9.9 before becoming the default key exchange in OpenSSH 10.0 ^{[11] [13] [14]}. Where it is least comfortable is its assumption: Module-LWE is younger and more structured than code- or hash-based hardness, which is the entire reason the field wants a non-lattice KEM in reserve.

6.2 ML-DSA (FIPS 204): the default signature#

ML-DSA is the standardized CRYSTALS-Dilithium, and it is the signature you should reach for by default ^{[3] [38]}. It builds on the same Module-LWE ring world as ML-KEM (here with $q = 8380417$), but it signs by a completely different route than the hash-and-sign that leaked in NTRUSign.

The signer commits to a masking vector $\mathbf{y}$, derives a sparse challenge $c$ by hashing the commitment together with the message, and forms $\mathbf{z} = \mathbf{y} + c\mathbf{s}_1$. If $\mathbf{z}$ strays outside a safe range, releasing it would leak the secret, so the signer aborts and tries again.

flowchart TD
A[Sample fresh masking vector y] --> B[Derive sparse challenge c by hashing commitment and message]
B --> C[Form candidate z as y plus c times secret s1]
C --> D{"Is z inside the safe range?"}
D -- No, would leak the secret --> A
D -- Yes --> E[Publish signature challenge, z, hint]

You can watch the loop behave. The number of attempts varies from signature to signature, and every released value stays inside the safe bound -- the mechanism that makes the transcript reveal nothing about the key.

// Illustrative only -- NOT production crypto.
// Keep sampling a masking value y until z = y + c*s1 lands in a safe range.
// Candidates that would correlate z with the secret are rejected; only
// key-independent z escape. Signing time therefore varies run to run.

const GAMMA1 = 100;   // masking range
const BETA   = 20;    // how far c*s1 can push z
const secret = 37;    // s1, unknown to the verifier
const c = 1;          // toy sparse challenge
const rand = (n) => Math.floor(Math.random() * n);

function signOnce() {
let attempts = 0;
while (true) {
  attempts++;
  const y = rand(2 * GAMMA1) - GAMMA1;       // uniform masking
  const z = y + c * secret;
  if (Math.abs(z) < GAMMA1 - BETA) return { z, attempts }; // safe -> release
  // otherwise abort and retry with fresh y
}
}

let total = 0, n = 20000, maxAbsZ = 0;
for (let i = 0; i < n; i++) {
const r = signOnce();
total += r.attempts;
maxAbsZ = Math.max(maxAbsZ, Math.abs(r.z));
}
console.log('avg attempts / signature:', (total / n).toFixed(2));
console.log('max |z| ever released   :', maxAbsZ, 'bound is', GAMMA1 - BETA);
console.log('variable attempt count is why ML-DSA signing time is not constant');

The Dilithium team chose this uniform-integer, rejection-based route deliberately, rather than Falcon's Gaussian sampler, and they were blunt about why.

"Gaussian sampling is hard to implement securely and efficiently." -- the CRYSTALS-Dilithium team, on why ML-DSA uses uniform integers and no floating point ^[38].

The private key / public key / signature sizes are 2560 / 1312 / 2420 for ML-DSA-44, 4032 / 1952 / 3309 for ML-DSA-65, and 4896 / 2592 / 4627 for ML-DSA-87, targeting NIST categories 2, 3, and 5 ^[3]. Verification is fast and constant-time; signing is fast but variable-time because of the abort loop, which is the single most important operational fact about the scheme. On Cortex-M4, ML-DSA-65 signing averages near 6.19M cycles but ranges from about 2.92M to 26.0M across a thousand runs ^[35].

ML-DSA excels as the general-purpose default: no floating point, easy constant-time code, moderate sizes, fast verification. Its weak spot is the signature-size wall this series flagged for interfaces in Part 17 on digital signatures -- a 3309-byte signature is roughly fifty times an Ed25519 signature, and that multiplies through certificate chains.

6.3 SLH-DSA (FIPS 205): the conservative backstop#

SLH-DSA is the standardized SPHINCS+, and it makes the most conservative bet in the toolkit: its security rests on nothing but the properties of its hash function, the same primitives this series covered in Part 10 on cryptographic hashes ^{[4] [39]}. If every lattice and code assumption fell tomorrow, a signature that depends only on a hash would still stand.

flowchart TD
M[Message digest] --> R[Randomizer picks a FORS instance pseudo-randomly]
R --> F[FORS few-time signature over the digest]
F --> W[WOTS+ one-time key authenticates the FORS root]
W --> H[Hypertree of Merkle layers, each signs the layer below]
H --> PK[Single long-lived public root]

The trade is stark. Public keys are tiny (32 to 64 bytes), but signatures are enormous and signing is slow. FIPS 205 defines twelve parameter sets -- three security levels, each with a "small" (s) and "fast" (f) variant, over SHA-2 and SHAKE. The public key / signature sizes run 32 / 7856 for 128s, 32 / 17088 for 128f, 48 / 16224 for 192s, 48 / 35664 for 192f, 64 / 29792 for 256s, and 64 / 49856 for 256f ^[4]. Signing hashes whole subtrees and costs hundreds of millions to billions of Cortex-M4 cycles, orders of magnitude slower than lattice signing ^[35]. The s/f knob only trades one pain for the other: smaller signatures mean slower signing.

That profile makes SLH-DSA the right tool for low-volume, high-assurance signing -- firmware, boot chains, and software-update roots -- where you sign rarely, verify occasionally, and value a rock-bottom assumption over compactness.

6.4 FN-DSA / Falcon: the compact hopeful (pre-final)#

Falcon instantiates the GPV hash-and-sign framework over NTRU lattices ($q = 12289$, dimension $n = 512$ or $1024$), and it produces the smallest signatures and keys of any standardized-track scheme ^{[41] [23]}.

flowchart LR
M[Message] --> HP[Hash message to a point c in the ring]
HP --> TS[Use NTRU trapdoor basis to target c]
TS --> GS[Fast-Fourier Gaussian sampling, the delicate floating-point step]
GS --> SV[Short vector s1, s2 near the lattice]
SV --> SIG[Signature is a salt plus compressed s2]

The payoff is compactness. Falcon-512 has an 897-byte public key and a 666-byte signature (roughly RSA-2048's classical security level, as this series discussed in Part 14, at a fraction of the byte size); Falcon-1024 is 1793 / 1280 ^[41]. On a desktop i5-8259U the reference code signs about 5948 times per second and verifies about 27933 times per second for Falcon-512 ^[41]. A Falcon-512 signature is under a third the size of ML-DSA-44's.

So why is it the last of the five to standardize? Because the Gaussian sampler runs on floating-point arithmetic, and making floating point constant-time across compilers and CPUs is genuinely hard. Timing or precision leakage of the sampler's Gram-Schmidt norms can recover the secret key ^[8]. Mitigations exist -- Pornin's constant-time integer implementation and isochronous Gaussian sampling among them -- but they are intricate and platform-sensitive ^{[42] [43]}.

Falcon is the right tool when signature and key bandwidth is the binding constraint and you can guarantee a vetted constant-time implementation -- and even then, not before FIPS 206 lands. Until it does, prefer ML-DSA.

6.5 HQC: the non-lattice insurance policy (pre-final)#

HQC ("Hamming Quasi-Cyclic") is the toolkit's deliberate non-lattice hedge. Its security rests on the hardness of decoding random quasi-cyclic codes -- syndrome decoding, unrelated to lattices -- so a future lattice break would leave it untouched ^[44]. It solves the problem that sank BIKE by separating the secret from the decoder: HQC encrypts by adding a low-weight error and decodes with a public, fixed code (a concatenation of Reed-Muller and Reed-Solomon codes) whose decoding-failure rate can be bounded analytically and does not depend on the secret. That bounded, secret-independent DFR is exactly why NIST preferred it over BIKE ^{[6] [32]}.

The cost is bandwidth. The encapsulation key / decapsulation key / ciphertext / shared secret sizes are 2241 / 2321 / 4433 / 32 for HQC-1, 4514 / 4602 / 8978 / 32 for HQC-3, and 7237 / 7333 / 14421 / 32 for HQC-5 ^[44]. The ciphertext is roughly four to nine times ML-KEM's. HQC is the reserve KEM, not the first choice: you carry the extra kilobytes precisely because its assumption is unrelated to everything else in the box.

6.6 Tier C: the signposts#

Four more schemes sit just outside the toolkit and are worth knowing by name.

Classic McEliece is the most conservative code-based KEM, unbroken since 1978, but with public keys from roughly 261 KB to over a megabyte ^[27]. It was not selected for the FIPS set and is advancing on an ISO track; choose it only where a huge, static, long-lived key is acceptable and maximal conservatism is the goal.

BIKE is the quasi-cyclic KEM that HQC beat out; its secret-dependent decoding-failure rate was judged less mature than HQC's bounded public decoder, so NIST did not select it ^{[45] [6]}.

XMSS and LMS are the standardized stateful hash signatures -- compact, conservative, and safe only where perfect state is guaranteed ^[28].

CSIDH is the one post-quantum candidate for a non-interactive Diffie-Hellman-style shared key, but its quantum security is contested -- subexponential quantum attacks push it toward much larger parameters ^[46] -- and its isogeny cousin SIKE was broken in 2022 ^[9]. Treat it as research, not deployment.

Now the exact bytes, all in one place. The table below is the empirical anchor for every trade discussed next -- the literal number of bytes a protocol must carry for each choice.

Two footnotes complete the picture. For the KEMs, the decapsulation (secret) keys are larger than the encapsulation keys -- 1632 / 2400 / 3168 bytes for ML-KEM and 2321 / 4602 / 7333 bytes for HQC -- and both produce a 32-byte shared secret ^{[2] [44]}. For ML-DSA, the private keys are 2560 / 4032 / 4896 bytes ^[3]. Now the uncomfortable question: given all five, which do you actually deploy, and what do you give up to get it?

7. Choosing Inside the Toolkit#

There is no universal winner, and looking for one is the wrong frame. In practice you make two decisions -- which KEM, and which signature -- plus one deployment choice about hybrids. Everything else follows from the bytes in the master table and the assumption you are willing to trust.

The KEM decision is really ML-KEM versus HQC, because the other code-based options are signposts rather than shipping choices.

ML-KEM wins on size and ubiquity. HQC's entire reason to exist is that its assumption is unrelated to ML-KEM's, so a lattice break would not take both down -- and you pay roughly eight times the ciphertext for that insurance ^{[2] [44] [6]}.

The signature decision spans three finalists on very different paradigms.

There is no free lunch in that table ^{[3] [41] [4]}. Falcon is smallest but hardest to implement safely and not yet final; SLH-DSA is the safest to trust but by far the largest and slowest; ML-DSA is the sensible middle and the recommended default.

To feel the gap, anchor on the classical world this series has used throughout. An Ed25519 signature is 64 bytes; an X25519 public key is 32. Nothing in the post-quantum toolkit comes close, as Part 15 on elliptic curves makes vivid.

The smallest post-quantum signature, Falcon-512 at 666 bytes, is about ten times larger and carries a floating-point hazard; the most conservative, SLH-DSA-128s at 7856 bytes, is about one hundred and twenty times larger; and the default KEM ciphertext, ML-KEM-768 at 1088 bytes, is about thirty-four times an X25519 share ^{[41] [4] [2]}. Every column of these tables buys one property -- small size, easy constant-time code, a conservative assumption, or non-lattice diversity -- by giving up another.

No post-quantum primitive wins on every axis. The five are not a menu awaiting a single winner; they are deliberate coverage of a trade surface, chosen so that whatever your binding constraint -- bytes, speed, assumption conservatism, or implementation safety -- one of them is the defensible answer.

The toolkit is five points on a trade surface, not an arbitrary menu.

One more choice cuts across both decisions: hybrid versus pure. The shipping default, X25519MLKEM768, runs a classical X25519 exchange and a post-quantum ML-KEM-768 encapsulation together and combines both shared secrets, so the session stays secure as long as either half holds ^[11]. During a migration that is the conservative posture: it defends against a future quantum computer and against an implementation bug in the young post-quantum half at once -- a belt-and-suspenders design, the security-definition thinking of Part 1 made concrete. These trades feel like engineering. Underneath them sits something humbler: we cannot prove any of it is hard.

8. What We Cannot Prove#

Here is the headline most readers do not expect: none of the five rests on an unconditional hardness proof. "Standardized by NIST" does not mean "proven secure." It means "no efficient attack is known, backed by decades of failed attempts and, for lattices, an unusually strong reduction." That is a different and more honest claim.

The lattice story is the one people most often overstate. Ajtai and then Regev proved worst-case-to-average-case reductions: breaking random instances is as hard as breaking the worst case ^{[19] [21]}. That is remarkable, and it is genuinely reassuring.

But three caveats matter. First, those reductions are cleanest for plain LWE, while the standards use structured Module-LWE and NTRU, whose reductions are weaker or looser. Second, the actual parameters are not chosen from the reduction at all; they are sized against the best-known attack, lattice sieving, whose cost is heuristically $\approx 2^{0.292\beta}$ classically and roughly $2^{0.265\beta}$ quantumly under debated memory assumptions ^[47]. Third, at the approximation factors these schemes use, the underlying lattice problems sit in $\mathsf{NP} \cap \mathsf{coNP}$, so they are not NP-hard under standard assumptions ^[48]. A genuine super-polynomial lower bound for any of them would prove $\mathsf{P} \neq \mathsf{NP}$ -- which no one can currently do.

Codes and hashes are no different in kind. General syndrome decoding is NP-hard, but HQC's security depends on the average-case hardness of decoding random quasi-cyclic codes, which is an assumption, not a theorem ^[44]. SLH-DSA reduces tightly to standard properties of its hash function, with no algebraic structure to exploit -- the most conservative bet in the box, but still a bet ^[4].

Two results in this area are not assumptions but hard walls, and they pull in opposite directions. The first is Shor's algorithm itself: no choice of RSA, Diffie-Hellman, or elliptic-curve parameters can ever be post-quantum, because the attack is a capability of the adversary, not a bound you can tune ^[1]. The second constrains the replacements.

That second wall -- KEM is not NIKE -- is why post-quantum migration is not a mechanical find-and-replace. Any protocol that relied on Diffie-Hellman's non-interactive static-static agreement has to be redesigned around an interactive KEM handshake, as Part 18 on Diffie-Hellman foreshadowed. It is a design-level impossibility, not a tuning problem.

One more subtlety links two sections: for the FO-transformed KEMs, the decryption-failure rate is a security bound, not merely a correctness figure. A noticeable, secret-correlated failure rate is an oracle -- the exact mechanism behind the BIKE reaction attack -- which is why ML-KEM specifies rates like $2^{-164.8}$ and HQC insists on an analytically bounded one ^[32].

Put it all together and the shape of the toolkit becomes inevitable. The theoretically perfect primitive would have elliptic-curve-sized keys and signatures, fast constant-time software with no floating point, a conservative and well-understood assumption, and strong chosen-ciphertext or unforgeability guarantees. No known construction reaches all four corners at once: lattices are small and fast on a young, structured assumption; hashes are conservative but huge; codes offer diversity but cost kilobytes. The five primitives are the field's best simultaneous coverage of that surface. If we cannot prove hardness, the honest posture is to keep asking what we still cannot do -- and to keep a spare.

9. The Frontier the Toolkit Does Not Close#

A field guide should be honest about what remains open. Seven problems sit on the near horizon, and together they explain why the toolkit is best understood as a monitored bet with an insurance policy attached.

The signature-size wall. No post-quantum signature reaches the 64-byte classical world while keeping a conservative assumption and an easy constant-time implementation. Falcon-512 is 666 bytes but floating-point; ML-DSA-44 is 2420 bytes; SLH-DSA-128s is 7856 bytes and up. Certificate chains, TLS handshakes, DNSSEC responses, and firmware manifests all multiply signature size by depth, so a few-kilobyte signature reshapes protocols. NIST's ongoing "Additional Digital Signature Schemes" on-ramp is the active response, hunting for small-signature options on different assumptions ^[12]. This on-ramp is deliberately looking beyond lattices -- for schemes whose assumptions differ from ML-DSA and Falcon -- so that a future small-signature standard also widens the toolkit's assumption diversity rather than deepening its lattice exposure.

Constant-time Falcon without floating point. Falcon's fast-Fourier Gaussian sampler is defined over floating-point arithmetic, and a portable, high-precision, provably constant-time sampler is hard to guarantee across compilers and CPUs. This is the chief obstacle to shipping FN-DSA safely and the reason it standardizes last ^{[42] [43]}. The motivating attack -- key recovery from Gram-Schmidt norm leakage -- is concrete, not hypothetical ^[8].

Shrinking code-based ciphertexts. HQC buys assumption diversity at 4.4 to 14.4 KB ciphertexts, and the smaller-key alternative (BIKE) was set aside precisely because its secret-dependent failure rate is a reaction-attack surface. An open goal is a code-based KEM with McEliece-like conservatism, ML-KEM-like size, and a provable secret-independent DFR ^[6].

Formally verified, side-channel-hardened implementations of all five. KyberSlash showed that even widely used reference code can leak through timing ^[7]. Machine-checked constant-time implementations of ML-KEM exist, but ML-DSA's variable-time abort loop and FN-DSA's floating point are materially harder to verify end to end. The standards are only as safe as the code that runs them.

Is the algebraic structure free? Ring-LWE, Module-LWE, and NTRU all add ring structure for compact keys and fast transforms. No attack exploits that structure at the standardized parameters, but there is no proof it is as hard as unstructured LWE -- and all three lattice primitives share the exposure, so a structural breakthrough could touch most of the toolkit at once. The Module-LWE design dilutes structure as a hedge, but the conjecture that it is essentially as hard as plain LWE remains believed and unproven.

Migrating static-static protocols. Because a KEM is not a NIKE, any protocol that assumed non-interactive Diffie-Hellman agreement must be redesigned, not reconfigured. Interactive hybrid handshakes cover key establishment well; a practical, trusted post-quantum NIKE does not exist.

The real quantum cost of sieving. The quantum sieving exponent near $2^{0.265\beta}$ depends on memory and qRAM models whose real-world cost is uncertain, and NIST's security categories inherit that uncertainty ^[47]. Conservative defaults -- recommending Category-3 ML-KEM-768 rather than the smaller set -- absorb the doubt, but a settled cost model would tighten every lattice parameter.

None of that blocks you from shipping the right thing today. Here is exactly what to ship.

10. Exact Decision Rules#

Enough theory. Here are defensible defaults you can carry into a design review, phrased as "use X with these parameters in case Y."

flowchart TD
Q1{"Signing or key exchange?"}
Q1 -- Key exchange --> K1{"Bandwidth very tight and Category 1 acceptable?"}
K1 -- Yes --> KEM512[ML-KEM-512 in a hybrid]
K1 -- No --> K2{"Long-term or Category 5 secret?"}
K2 -- Yes --> KEM1024[ML-KEM-1024 in a hybrid]
K2 -- No --> KEM768[ML-KEM-768 hybrid, the default]
Q1 -- Signing --> S1{"Low-volume firmware or root of trust?"}
S1 -- Yes --> SLH[SLH-DSA-128s or 128f]
S1 -- No --> S2{"Is signature size the hard limit?"}
S2 -- No --> MLDSA[ML-DSA-65, the default]
S2 -- Yes --> FN[Consider FN-DSA, vetted constant-time only, after FIPS 206]

• Key establishment (TLS, SSH, VPN): use ML-KEM-768 in a hybrid (X25519MLKEM768). It is the shipping default and the conservative middle category ^{[11] [13]}. Drop to ML-KEM-512 only under tight bandwidth with Category-1 acceptance; step up to ML-KEM-1024 for Category-5 or long-lived secrets.
• General-purpose signatures: use ML-DSA-65 (Category 3). No floating point, easy constant-time, moderate sizes ^[3].
• Firmware, boot, root-of-trust (low volume, maximum conservatism): use SLH-DSA-128s for smaller signatures or 128f for faster signing. You sign rarely, so absorb the large signature in exchange for a hash-only assumption ^[4].
• When signature size is the binding constraint: consider FN-DSA / Falcon -- but only with a vetted constant-time implementation, and not in production until FIPS 206 is final ^[5]. Until then, prefer ML-DSA.
• For KEM assumption diversity: plan for HQC as a standardized non-lattice backup once its FIPS lands, not today ^[6]. If you need maximal conservatism now and can absorb a huge static key, Classic McEliece is the code-based option outside the FIPS set ^[27].

The single most useful thing you can build is an intuition for how many bytes each choice adds. Run the numbers.

// Illustrative only. Estimate the extra bytes post-quantum adds versus classical
// X25519 / Ed25519, for a KEM share and for a 3-certificate chain.

const sizes = {
'Ed25519':      { sig: 64,   pk: 32 },
'ML-DSA-65':    { sig: 3309, pk: 1952 },
'Falcon-512':   { sig: 666,  pk: 897 },
'SLH-DSA-128s': { sig: 7856, pk: 32 },
};

// A chain of 3 certificates, each carrying one signature + one public key.
function chainBytes(name) {
const s = sizes[name];
return (s.sig + s.pk) * 3;
}

for (const n of ['Ed25519','ML-DSA-65','Falcon-512','SLH-DSA-128s']) {
console.log(n.padEnd(14), String(chainBytes(n)).padStart(6), 'bytes over a 3-cert chain');
}

console.log('---');
const x25519Share = 32 + 32;            // classical key share, round trip
const mlkemAdds   = 1184 + 1088;        // ML-KEM-768 key + ciphertext
console.log('KEM share, classical X25519 :', x25519Share, 'bytes');
console.log('KEM share, ML-KEM-768 hybrid:', x25519Share + mlkemAdds, 'bytes');

Rules pick the primitive; discipline keeps it safe. A short pitfall list, drawn straight from the failure catalog:

• Do not divide a secret by the modulus in variable time. That was KyberSlash; use constant-time (Barrett) reduction and a library whose constant-time behavior has been tested ^[7].
• Prefer hedged (randomized) signing for ML-DSA, and feed it a good RNG. The randomized mode is the default and is more resilient to fault and nonce mishaps ^[3].
• Use context strings to domain-separate signatures across applications and prevent cross-protocol reuse ^[3].
• Keep implicit rejection constant-time. Never let a KEM surface a decapsulation failure as a distinguishable error or timing tell.
• Do not hand-roll any of these. Every primitive has subtle side channels; use standard libraries.

On availability: the finalized three are production-ready across the toolchain. OpenSSL 3.5 ships X25519MLKEM768 as a default key share, OpenSSH enabled mlkem768x25519-sha256 by default in 9.9 and made it the default in 10.0, and ML-KEM and ML-DSA are broadly available across open-source libraries -- liboqs, BoringSSL, AWS-LC, Microsoft SymCrypt, Bouncy Castle, and pyca/cryptography -- with formally verified ML-KEM through the libcrux line ^{[11] [14] [49]}. FN-DSA and HQC are experimental only until their FIPS documents are final. For a sense of how this looks in real deployments, this blog's companion posts trace the post-quantum migration on Windows and the moment ML-KEM arrived in an ordinary pip install. The forthcoming Part 21 on crypto-agility and cryptographic bills of materials covers how to keep these choices swappable as the toolkit evolves.

The rules above answer "what." These next answer the questions that come up in review.

11. Questions From the Review Room#

Step back to the shape of the whole thing. One event in 1994 condemned all deployed public-key cryptography ^[1]. The field's answer was not a single replacement but a portfolio hedged across three unrelated assumptions and tuned to five different binding constraints, three of them already law and two still in progress. The most striking fact remains the quietest one: after a decade of open, adversarial cryptanalysis, nothing in the toolkit has been broken -- only its early code has leaked.

The real test is still ahead. When the next break comes, and history suggests one eventually will, the entire point of this design is that it lands on one assumption family while the others carry the load. That is not a promise that the math is unbreakable. It is a bet, made in the open, that diversity outlasts any single idea -- and a spare, HQC, waiting in reserve for the day the bet is called.