How the NIST Finalists Broke: Rainbow in a Weekend, SIKE in an Afternoon, and the Graveyard of Post-Quantum Candidates

1. Rainbow in a weekend, SIKE in an afternoon#

Over one weekend in February 2022, a laptop -- an ordinary one -- recovered the secret key of Rainbow, a digital-signature scheme that had survived five years of public scrutiny to stand as one of three finalists in NIST's competition to choose the cryptography that will outlive the quantum computer ^[1]. Five months later, a second NIST candidate named SIKE fell in about ten minutes on a single processor core -- and not to a quantum computer, but to a theorem published in 1997, before the scheme it destroyed had even been invented ^[2].

Neither break was a bug in the code, a leaked random number, or a padding mistake. Both were the mathematics of the primitive itself coming apart in public. And, improbably, that was the plan all along.

That sentence should stop you. Every earlier part of this series, "How It Breaks in Real Life," told the same reassuring story from a different angle: the mathematics held, and the machine around it leaked -- a predictable nonce, a downgrade, a validation bug, a random-number generator that was not random. The primitive almost never broke. This is the one chapter where it did. Rainbow and SIKE were not broken by their implementations. They were broken by their own algebra, on schedule, by a global research community that had been invited to try.

A public cryptographic competition is not a bracket that picks the best design. It is an industrial-scale cryptanalysis engine. It runs unproven new primitives at the entire research community until the weak ones break on paper -- cheaply, classically, in the open -- so that the survivors are trusted not because anyone proved them secure, but because they are the ones nobody could break in time. Trust by attrition, not by proof.

Two facts of precision matter before we go further, because the popular retellings blur them. Rainbow was a genuine finalist: one of three signature schemes NIST named as finalists in July 2020, the last stop before standardization ^[3]. SIKE was not. SIKE was an alternate that advanced to a fourth round of study in July 2022 for its unusually small keys; it was never a finalist ^[4]. The distinction is load-bearing. "Finalist" means Rainbow was on the short list NIST was prepared to standardize. "Alternate" means SIKE was kept in reserve. Both were vetted, public, and taken seriously -- which is exactly why their falls are evidence and not embarrassment. The gap between them is part of the point: two schemes at different tiers of the same competition, broken by two unrelated ideas, weeks apart.

One more honesty note frames everything below. These are not production incidents. There is no CVE for Rainbow, no vendor advisory for SIKE, no breach report. The incident class here is different and, for cryptographers, more interesting: the documented cryptanalytic collapse of candidate primitives during standardization, each grounded in its primary academic paper and the matching NIST status report. Nobody's data was stolen. Two pieces of proposed mathematics were shown, in public, to be weaker than their designers claimed.

"Rainbow is one of the three finalist signature schemes... our attack returns the corresponding secret key after on average 53 hours (one weekend) of computation time on a standard laptop." -- Ward Beullens, Breaking Rainbow Takes a Weekend on a Laptop, 2022

To see why two schemes this scrutinized could fall this cheaply -- and why cryptographers half-expected something like it -- you have to start with the thing that forced us onto young, untested mathematics in the first place.

2. Why hold a competition at all?#

In 1994, Peter Shor proved that a large enough quantum computer could factor integers and compute discrete logarithms in polynomial time ^[5]. That single result condemned almost all of the public-key cryptography the internet runs on. RSA, Diffie-Hellman, and elliptic-curve cryptography all rest on exactly those two problems, so they all die at once -- someday, when the hardware exists. The public-key internet was suddenly living on borrowed time.

The replacements had to come from somewhere else: hard problems with no known quantum shortcut. Five families volunteered. Lattices (find a short vector in a high-dimensional grid), error-correcting codes (decode a random-looking linear code), multivariate quadratics (solve a big system of quadratic equations over a finite field), isogenies (find a secret map between elliptic curves), and hash functions (invert nothing, just chain one-way functions together). Each family offered a problem believed to resist both classical and quantum attack.

Here is the tension the whole story turns on. "No known quantum attack" is a far weaker statement than "no known attack." These five families were young. Their classical security -- how they hold up against ordinary, non-quantum mathematics -- had been studied for years, not the decades of relentless attention that number theory had absorbed since RSA in 1977. Swapping a well-understood problem for a poorly-understood one to dodge a future threat is a trade that quietly imports a present risk. You have escaped Shor, but you have moved onto ground nobody has finished mapping.

NIST's answer to that imported risk was procedural, not mathematical: convert unknown risk into public cryptanalysis. In December 2016 it issued a formal Call for Proposals for post-quantum KEMs and signatures, with a submission deadline of 30 November 2017 ^[6]. By that deadline, 82 algorithms had been submitted; 69 met the acceptance criteria and were posted as first-round candidates on 20 December 2017, spread across all five families ^[7]. The competition had begun with 69 live bets on unproven mathematics.

timeline
title NIST PQC competition and the breaks it produced
2016 : NIST issues the Call for Proposals
2017 : 82 submissions, 69 first-round candidates
2019 : Round 2 narrows the field to 26
2020 : Round 3 names 7 finalists and 8 alternates : Rainbow a finalist, SIKE an alternate
2022 : Rainbow key-recovered in February : SIKE advances to Round 4 in July : SIKE key-recovered in July and August : first four standards selected
2024 : FIPS 203, 204 and 205 published in August
2025 : HQC selected as the fifth standard

Shor is the reason this contest exists, but his algorithm plays no further part in what follows. The mechanics of Shor's algorithm -- period-finding, the quantum Fourier transform, why a working quantum computer would end RSA -- belong to the companion "Q-Day" piece in this series. Here Shor is motivation only. Every break in this article is classical. None of the breaks below use a quantum computer. That is worth holding onto, because it is easy to assume "post-quantum scheme broken" means "broken by a quantum machine." It means the opposite: these schemes were supposed to resist quantum computers, and they fell to ordinary ones.

NIST had run this exact play twice before, with AES in the late 1990s and SHA-3 a decade later ^{[8, 9]}. Both times the goal was not to pick the cleverest design on paper -- it was to let the whole world attack every design until the weak ones fell. That is a stranger idea than it sounds, and it is worth taking seriously on its own terms.

3. A broken scheme is a deliverable, not a scandal#

Reframe the whole exercise this way: in an open cryptographic competition, a broken candidate is not a failure. It is a product. The question the competition asks is never "will any of these schemes break?" -- of course some will -- but "how far does each one get before it does?" A scheme that breaks in Round 1 has done its job by revealing a bad idea cheaply. A scheme that survives to Round 3 and then breaks has done something more useful: it has told the community that an idea which looked strong for years was still not strong enough.

This is the interpretive key to everything that follows, so it deserves a name.

Read against that definition, the funnel of the NIST competition is not a story of disappointing losses. It is the machine running. Sixty-nine first-round candidates narrowed to 26 in the second round, then to 15 in the third -- seven finalists and eight alternates -- then to a handful of standards ^[7]. Each narrowing is a batch of schemes that either broke, weakened under analysis, or lost on performance to a survivor. The attrition rate is the yield of the engine, and you can compute it directly.

// NIST PQC standardization, headcount at each stage
const rounds = [
{ name: 'Submitted 2017', count: 82 },
{ name: 'Round 1 accepted', count: 69 },
{ name: 'Round 2', count: 26 },
{ name: 'Round 3 (7 finalists + 8 alternates)', count: 15 },
{ name: 'Selected for standardization by 2025', count: 5 },
];

for (let i = 1; i < rounds.length; i++) {
const prev = rounds[i - 1];
const cur = rounds[i];
const rate = ((cur.count / prev.count) * 100).toFixed(0);
console.log(prev.name + ' -> ' + cur.name + ': ' + cur.count + ' of ' + prev.count + ' survived (' + rate + '%)');
}

// The signature cohort specifically: 9 schemes entered Round 2, only 3 reached standardization
const sigStart = 9, sigSurvived = 3;
const sigRate = ((sigSurvived / sigStart) * 100).toFixed(0);
console.log('Signatures: ' + sigSurvived + ' of ' + sigStart + ' Round-2 schemes survived = ' + sigRate + '%');

// End to end
console.log('Overall: ' + ((5 / 82) * 100).toFixed(1) + '% of submissions reached standardization');

Run it and the abstraction becomes concrete. Two-thirds of the signature schemes that reached the second round did not survive to standardization. "New-primitive breaks are frequent" stops being a slogan and becomes a measured survival rate.

So let us walk the graveyard the way the competition actually produced it -- round by round -- and watch two entire families of "quantum-proof" mathematics come apart.

4. The graveyard, round by round#

Picture the competition as a funnel. Eighty-two schemes go in at the top; five come out the bottom as standards. In between, the walls of the funnel are lined with the schemes that did not make it -- and the two families we are about to follow were not merely thinned. They were emptied.

flowchart TD
A["82 submissions in 2017"] --> B["69 first-round candidates"]
B --> C["26 second-round candidates"]
C --> D["15 in Round 3: 7 finalists and 8 alternates"]
D --> E["4 selected in 2022"]
E --> F["5th standard HQC in 2025"]
D --> G["Rainbow: finalist, broken February 2022"]
D --> H["SIKE: alternate to Round 4, broken July 2022"]

Round 1 was a high-throughput first pass. Between the December 2017 opening and the January 2019 cut to 26, a steady stream of first-round candidates fell to analysis, and many of the losses were individually minor -- a parameter set adjusted here, a scheme withdrawn there ^[7]. This is the engine idling at full speed: cheap early breaks that cost a preprint apiece and cleared out the obviously fragile before serious attention concentrated on the rest. The interesting deaths came later, once schemes had earned enough trust that breaking them actually meant something.

The multivariate family thins#

To watch the first family die, you need one black-box idea.

It does, and the family's history is a chain of such fingerprints. Jacques Patarin's balanced Oil-and-Vinegar was broken by Aviad Kipnis and Adi Shamir in 1998 ^[10], which forced the unbalanced redesign published as UOV in 1999 ^[11]; a separate big-field branch, Hidden Field Equations, had appeared in 1996 ^[12].

The first casualty of the NIST era itself was LUOV, a "lifted" Unbalanced Oil-and-Vinegar scheme whose public map was defined cleverly over the field with two elements to shrink keys. In December 2019, Jintai Ding and colleagues showed that this lifted structure could be pushed down into a smaller subfield, dropping the cost of key recovery below the security levels LUOV had claimed ^[13]. LUOV did not survive to the third round.

A year later, in November 2020, the other surviving multivariate signature -- GeMSS, a Round 3 alternate built on the big-field HFE branch of the family -- was key-recovered by Chengdong Tao, Albrecht Petzoldt, and Jintai Ding, who showed the scheme's "Minus" and "Vinegar" modifiers added essentially no security and left GeMSS "not as secure as claimed" ^[14].

Two more signatures, MQDSS (multivariate) and qTESLA (lattice-based), dropped out at the Round 3 selection without a single dramatic break paper: MQDSS under pressure on its five-pass Fiat-Shamir construction, qTESLA superseded on size and performance by the lattice signatures Dilithium and Falcon. NIST's status report records their elimination; honesty requires noting there is no verified key-recovery paper for either, only the competition quietly declining to advance them ^[3]. The family was being emptied from several directions at once.

flowchart TD
OV["Oil and Vinegar, 1997"] -->|Kipnis-Shamir break, 1998| UOV["Unbalanced Oil and Vinegar, 1999"]
UOV --> RB["Rainbow: layered UOV 2005, broken 2022"]
UOV --> LUOV["LUOV: lifted UOV, broken 2019"]
UOV --> SURV["Plain UOV and MAYO: survive"]
HFE["Hidden Field Equations, 1996"] --> GEMSS["GeMSS and HFEv-, broken 2020"]

One person threads through this whole graveyard, and the irony is worth pausing on. Ward Beullens co-designed LUOV, one of the schemes the multivariate family lost. He then wrote the attacks that weakened and broke Rainbow, the family's finalist. He now designs MAYO, a plain-UOV revival competing in NIST's signature on-ramp. The same researcher helped build, dismantle, and rebuild the family across a decade -- which is exactly what a healthy cryptanalytic community looks like. By late 2020, every multivariate signature in the competition except one had been broken or dropped. The exception was sitting on the finalist podium.

Rainbow: weakened, then broken#

Rainbow is a layered Unbalanced Oil-and-Vinegar scheme designed by Jintai Ding and Dieter Schmidt in 2005 ^[15]. Stacking several Oil-and-Vinegar maps in layers let it shrink its keys and signatures, which is exactly why it was competitive enough to reach the finalist round in 2020. That layering is also the extra structure the attack would grip.

The break came in two acts. In October 2020, while Rainbow sat among the three signature finalists, Ward Beullens published two new attacks -- an "intersection" attack and a "rectangular MinRank" attack -- that reduced the cost of Rainbow key recovery by factors reported as large as $\,2^{73}$, enough to show that every submitted Rainbow parameter set fell short of the NIST security level it claimed ^[16]. Rainbow was wounded but not yet dead; NIST kept it as a finalist while its parameters were re-examined.

Then, in February 2022, Beullens finished the job. Building on the same rectangular-MinRank idea, he recovered a full Rainbow secret key for the level-1 parameters in, on average, 53 hours -- one weekend -- on a standard laptop ^[1]. Not a supercomputer. Not a cluster. A laptop, over a weekend. With that, the multivariate signature cohort as submitted to NIST was effectively extinct.

Round 4: SIKE, and the 1997 theorem#

The second family died faster and more strangely. To follow it you need two more black-box ideas.

On 5 July 2022, NIST selected its first four standards and advanced four KEMs -- including SIKE -- into a fourth round for continued study ^[4]. SIKE went in as an alternate, attractive for its small keys, never a finalist ^[19].

Twenty-five days later, on 30 July 2022, Wouter Castryck and Thomas Decru posted a classical key-recovery attack on SIDH that broke SIKEp434 -- the level-1 parameter set -- in about ten minutes on a single core ^[2]. Their method rested on a reducibility criterion Ernst Kani had proved in 1997, a pure result about when a genus-2 curve's Jacobian splits into a product of elliptic curves, written 14 years before SIDH existed and with no cryptographic intent whatsoever ^[20]. The attack fed SIDH's published torsion-point images into Kani's criterion and reconstructed the secret walk step by step. The timing is the thesis in miniature: SIKE advanced on 5 July 2022 and was broken on 30 July 2022. Twenty-five days as a NIST Round 4 candidate, then key-recovered on one processor core. The competition did not fail to catch SIKE. The competition caught SIKE, precisely on the schedule an open cryptanalytic process runs on.

What happened next is why the isogeny KEM line did not merely stumble but collapsed. Within nine days, Luciano Maino and Chloe Martindale removed the attack's dependence on SIKE's special starting curve, generalizing it to an arbitrary starting curve at subexponential cost ^[21]. Two days after that, on 10 August 2022, Damien Robert closed the door completely: SIDH can be broken in classical polynomial time, even from a random starting curve ^[22]. Eleven days, three papers, and an entire family of key exchange was finished.

One more clarification keeps the record honest. A separate SIKE attack, Hertzbleed, had been disclosed about six weeks earlier, on 14 June 2022 -- but that was a frequency side channel leaking keys from an implementation, an entirely different failure class that belongs to the implementation-break sibling in this series, not to the mathematics break we are tracing here ^[24]. Keeping the two apart is essential to the series' argument. Hertzbleed is "the machine leaked." Castryck-Decru is "the math broke." They happened to hit the same scheme six weeks apart, which makes the contrast unusually clean.

Two families, emptied by two ideas. Strip away the scheme names and the same shape appears in both: the exact feature that made each scheme competitive -- Rainbow's layering, SIDH's published torsion images -- is the exact feature the attack used to break it. That pattern is the real story, and it is worth slowing down to see clearly.

5. Two ideas, and the idea behind them#

Great cryptanalytic breaks are almost never brute force. They are a change of viewpoint -- a moment where someone looks at a public key and sees a different, easier problem hiding inside it. Both 2022 breaks are one sentence long once you see them. Here is each, made legible without the heavy machinery.

Rainbow: the low-rank fingerprint#

Start with what a multivariate public key actually is. Each of its quadratic equations can be written as a symmetric matrix, so the public key is a list of matrices $P_1, P_2, \ldots, P_m$. Rainbow's hidden trapdoor -- the layered oil-and-vinegar structure that lets the signer invert the system -- forces something specific to be true about those matrices: a particular linear combination $\sum_i x_i P_i$ of them has unusually low rank. Find that low-rank combination and you have found a shadow of the secret.

Beullens' insight was to reshape Rainbow's specific layered structure as a rectangular MinRank instance -- a form of the problem that is dramatically easier to solve than the general case -- and to combine it with an "intersection" step on the scheme's oil subspaces. Together these collapse the search space until the secret key falls out on commodity hardware ^{[16, 1]}. The move that matters is subtle and central: Rainbow's layering was added to make keys small, and that same layering is the low-rank structure the attack reads. The optimization did not sit alongside the vulnerability. The optimization was the vulnerability.

flowchart LR
A["Read the public key as quadratic forms, i.e. matrices"] --> B["Use Rainbow's layering to set up a rectangular MinRank instance"]
B --> C["Solve MinRank: find the low-rank combination"]
C --> D["Recover the hidden oil subspace"]
D --> E["Peel the layers, recover an equivalent secret key"]

None of this was born in 2022. MinRank has been the murder weapon of the multivariate family since 1999, when Aviad Kipnis and Adi Shamir showed that recovering the key of the HFE cryptosystem reduces to a MinRank instance ^[25]. Every subsequent optimization of the family -- layering in Rainbow, lifting in LUOV, the modifiers in GeMSS -- added structure that some MinRank-flavored attack could eventually grip. Beullens did not invent a new weapon. He found a better way to aim an old one.

SIKE: the data the protocol had to publish#

The SIKE break has the same shape, dressed in different mathematics. Recall that SIDH cannot run without publishing the torsion-point images -- the images of fixed public points under each party's secret isogeny. That auxiliary data is not optional; it is what makes the key exchange combine correctly. Castryck and Decru's move was to feed exactly that data into a criterion Kani proved in 1997.

flowchart LR
A["Take the torsion-point images SIDH publishes"] --> B["Build an auxiliary higher-dimensional isogeny from them"]
B --> C["Apply Kani's criterion: does it split as a product?"]
C --> D["Each split confirms a piece of the secret walk"]
D --> E["Walk the secret isogeny to full key recovery"]

Robert soon proved the general version runs in classical polynomial time from any starting curve ^[22]. And the warning had been on the record for years: in 2017, Christophe Petit had explicitly shown that the extra torsion-point information SIDH exposes makes its underlying problem easier, a five-year flare that the field noticed but could not yet turn into a full break ^[23].

The lever, again, was the feature. SIDH published torsion images because it had to; that requirement is what Kani's criterion turned into a key. And the criterion itself is the most striking detail of the whole affair. Kani wrote his 1997 paper about the number of genus-2 curves with elliptic differentials. It had no cryptographic purpose. The mathematical object that would recover a SIKE key in ten minutes sat, fully formed, in a number-theory journal for 25 years, waiting for someone to notice it applied.

The Castryck-Decru attack "breaks SIKEp434... in about ten minutes on a single core" -- and it does so with mathematics published before the scheme it destroyed existed.

The idea behind the ideas#

Step back and notice what neither break required. Neither Beullens nor Castryck-Decru invented exotic new machinery. Each recognized that mathematics already sitting in the literature -- MinRank reductions from 1999, Kani's criterion from 1997 -- applied to the specific structure the target scheme was forced to expose. The breakthrough was recognition, not invention.

The optimization was the leak. Rainbow's layering and SIDH's published torsion images were not incidental weaknesses next to the good parts of each design -- they were the good parts. Every feature that made these schemes competitive was structure, and structure is exactly what a cryptanalyst reads. The conservative, un-optimized ancestors survived; the clever, efficient descendants died.

This is what a competition industrializes. Cheap, public, classical cryptanalysis, run at global scale for years, is the machine that converts "we believe this is hard" into "this fell on a laptop." The competition is not the stage on which these breaks happened to occur. It is the instrument that produced them -- the reason someone finally looked at SIDH's torsion images through the lens of a 25-year-old theorem. If a machine this effective at breaking things left some schemes standing, the obvious question is what those survivors are, and whether we should trust them any more than we trusted Rainbow the week before it fell.

// A toy over GF(7): a random combination of matrices is full rank,
// but a "planted" combination (the trapdoor's shadow) is low rank.
const P = 7;
const mod = x => ((x % P) + P) % P;
const inv = a => { let r = 1, b = mod(a), e = P - 2; while (e > 0) { if (e & 1) r = mod(r * b); b = mod(b * b); e >>= 1; } return r; };

function rank(M) {
const rows = M.map(r => r.slice()), n = rows.length, m = rows[0].length;
let rk = 0;
for (let col = 0; col < m && rk < n; col++) {
  let piv = -1;
  for (let i = rk; i < n; i++) if (mod(rows[i][col]) !== 0) { piv = i; break; }
  if (piv < 0) continue;
  [rows[rk], rows[piv]] = [rows[piv], rows[rk]];
  const iv = inv(rows[rk][col]);
  for (let j = 0; j < m; j++) rows[rk][j] = mod(rows[rk][j] * iv);
  for (let i = 0; i < n; i++) if (i !== rk && mod(rows[i][col]) !== 0) {
    const f = rows[i][col];
    for (let j = 0; j < m; j++) rows[i][j] = mod(rows[i][j] - f * rows[rk][j]);
  }
  rk++;
}
return rk;
}

const n = 5;
const randVec = () => Array.from({ length: n }, () => Math.floor(Math.random() * P));
const outer = a => a.map(ai => a.map(aj => mod(ai * aj)));           // rank-1 symmetric
const add = (A, B) => A.map((r, i) => r.map((x, j) => mod(x + B[i][j])));
const sub = (A, B) => A.map((r, i) => r.map((x, j) => mod(x - B[i][j])));
const randSym = () => { const M = outer(randVec()); return add(M, outer(randVec())); };

// Plant a rank-2 target L = a a^T + b b^T, then force the sum of 4 matrices to equal it.
const L = add(outer(randVec()), outer(randVec()));                  // rank <= 2
const mats = [randSym(), randSym(), randSym()];
mats.push(sub(L, add(add(mats[0], mats[1]), mats[2])));             // now mats sum to L

const combine = (c) => mats.reduce((acc, Mk, k) =>
acc.map((r, i) => r.map((x, j) => mod(x + c[k] * Mk[i][j]))),
Array.from({ length: n }, () => new Array(n).fill(0)));

const randCoeffs = Array.from({ length: 4 }, () => 1 + Math.floor(Math.random() * (P - 1)));
console.log('rank of a random combination   :', rank(combine(randCoeffs)));   // typically 5
console.log('rank of the planted combination:', rank(combine([1, 1, 1, 1]))); // 2 -- the fingerprint

6. The survivors, and why we provisionally trust them#

On 13 August 2024, NIST published the survivors: the first three finalized post-quantum standards ^[26]. It is worth being precise about what they are. They are not the schemes that were proven safe -- none of them were. They are the schemes that nobody could break in time.

Three came first. ML-KEM (FIPS 203) ^[27], the key-encapsulation mechanism derived from CRYSTALS-Kyber ^[28], is the lattice workhorse: keys and ciphertexts of roughly one kilobyte, fast enough to be a near drop-in for elliptic-curve key agreement. ML-DSA (FIPS 204) ^[29], from CRYSTALS-Dilithium ^[30], is the default signature, chosen for a balance of size, speed, and implementation safety.

SLH-DSA (FIPS 205) ^[31], from SPHINCS+ ^[32], is the conservative hedge: it signs using nothing but hash functions, so its keys are tiny (32 to 64 bytes) but its signatures are enormous and slow, running from about 8 kilobytes to nearly 50. A fourth lattice signature, FN-DSA (Falcon), is still in draft as FIPS 206 -- it produces the smallest signatures of the group but is delayed because its floating-point sampling is hard to implement safely ^[33].

The two code-based KEMs tell the conservatism story most clearly. Classic McEliece rests on the hardness of decoding a random-looking linear code -- a scrambled binary Goppa code assumed indistinguishable from random -- an idea Robert McEliece proposed in 1978; the cost of the best attack against it has barely moved in more than 45 years of trying ^[34], and its one-way encryption is turned into a modern key-encapsulation mechanism by a tight security reduction ^[35]. Its price is a public key measured in hundreds of kilobytes to well over a megabyte, which is why NIST in 2025 declined to standardize it directly and deferred to an ISO effort already underway ^[36].

Its structural cousin HQC, based on decoding quasi-cyclic codes, was selected in March 2025 as the fifth standard ^[37]. HQC is the second KEM NIST standardized, and its selection is a deliberate hedge: if a structural idea ever breaks the lattice assumption under ML-KEM, HQC is a code-based fallback resting on entirely different mathematics. A portfolio only insures you if its members can fail independently.

The on-thesis reading of this list is the whole point of the section. "State of the art" here does not mean "proven best." It means residue of attrition -- the primitives the offensive engine of the last decade could not reach in time. That distinction is not academic hand-wringing. It is the honest status of every algorithm now being deployed at internet scale: ML-KEM hybrids already carry real traffic in Chrome, Cloudflare, Apple's iMessage PQ3, and Signal, and the migration is accelerating on the assumption that these schemes will hold ^[33].

There is one more thing the word "survived" hides. These schemes survived as several separate bets, not one. To see why NIST standardized a whole portfolio rather than crowning a single winner, you have to look at the five families side by side -- and pay attention to which two are missing.

7. Five families, five bets#

NIST never intended to crown one algorithm. It intended to place several independent bets on unrelated mathematics, so that a single new idea could not sink the entire standard at once. Read that way, the competition is a portfolio, and 2022 was the year two of its holdings went to zero. The value of the diversification stopped being a hypothetical and started paying out in real time.

Walk the five families by how much of the engine each one survived.

Lattices are the biggest bet, and they held. Module-LWE was the most-attacked young assumption in the whole competition, and it produced the KEM and the default signature. It survived not by being old but by absorbing the most punishment and still standing. Codes survived by pedigree: Classic McEliece has been under attack since 1978, and HQC gives the standard a second, structurally distinct code-based option ^[34]. Robert McEliece proposed his code-based cryptosystem in 1978, one year after RSA -- and unlike RSA, it has no known quantum shortcut. Its best attack has barely improved in more than four decades ^[38]. The conservatism dividend is real: the oldest idea in the room is the one nobody has laid a finger on. Hashes survived by minimalism: SLH-DSA assumes only that a hash function behaves like a hash function, the most conservative bet available.

The other two families are the graveyards we walked. Multivariate signatures are near-extinct in their submitted forms: Rainbow, GeMSS, LUOV, and MQDSS are all gone, emptied by the MinRank weapon and by competitive pressure. Isogeny key exchange collapsed with SIDH and SIKE.

flowchart TD
ROOT["Five hard-problem families"] --> LAT["Lattices: survived (ML-KEM, ML-DSA)"]
ROOT --> COD["Codes: survived (Classic McEliece, HQC)"]
ROOT --> HSH["Hashes: survived (SLH-DSA)"]
ROOT --> MV["Multivariate: pruned by MinRank"]
ROOT --> ISO["Isogeny KEM: pruned by Kani's criterion"]
MV --> MVD["Rainbow, GeMSS, LUOV dead"]
ISO --> ISOD["SIKE dead, CSIDH and SQIsign survive"]

But "family dead" is too coarse, and the nuance is the most instructive part. Within the isogeny family, the collapse was specific to schemes that publish torsion-point images. CSIDH, a commutative isogeny scheme, does not publish that data, so Kani's lever never reaches it ^[39]. SQIsign, an isogeny signature built from endomorphism rings rather than torsion images, also survives, and it offers the smallest post-quantum signatures of any candidate ^[40]. SIDH fell; two of its cousins are still standing. The multivariate family shows the same pattern in reverse: plain, un-optimized Unbalanced Oil-and-Vinegar with its large keys resists MinRank, and Beullens' own MAYO -- a plain-UOV revival -- is now competing in NIST's signature on-ramp ^[41]. The clever descendants died. The conservative ancestors lived.

The Round 3 record makes the diversification argument concrete. When Rainbow and SIKE were named finalist and alternate respectively, they were live bets ^[3]. When they broke, the standard did not break with them, because the other bets were still there ^[4]. That is the entire case for a portfolio, demonstrated under fire.

NIST did not fail to pick a single winner. It refused to bet the internet's future on one idea -- and in 2022, two of its five ideas proved exactly why that refusal was wise.

A portfolio hedges against surprise. What it cannot do is prove that anything in it is safe -- and it is worth being precise about exactly what all this attrition does and does not buy us.

8. What a competition can prove, and what it cannot#

Here is the sentence the whole field quietly lives with: not one of the survivors has been proven secure. Not ML-KEM, not ML-DSA, not SLH-DSA, not any of them. Every one rests on an assumption that no one has proved -- that Module-LWE is hard, that syndrome decoding is hard, that the underlying hash behaves ideally. Attrition gave us strong evidence for those assumptions. It gave us no proof.

Lattices have the best theoretical footing in the portfolio, and it is worth understanding exactly how far that footing extends -- because it stops short of where intuition wants it to go. Lattice schemes enjoy a worst-case-to-average-case reduction: Regev's original result, extended to module lattices by Langlois and Stehle, shows that breaking a random instance of Module-LWE is at least as hard as solving certain lattice problems in the worst case ^[42]. That is a genuinely strong guarantee, and no other family has anything like it.

But read the fine print. The reduction lands on module-lattice problems, a restricted class, and the quantum hardness of even those problems is itself unproven. That reduction is also asymptotic and, in its original form, quantum: it vouches for the family's structure, not for the concrete parameters ML-KEM and ML-DSA actually ship. Codes and multivariate schemes have no average-case reduction at all; their security is precisely "no one has found a good enough attack yet."

What sets the other boundary is complexity theory itself. The best known attacks are the yardsticks the parameters are chosen against: lattice sieving at a heuristic cost of $\,2^{0.292\,\beta + o(\beta)}$ in the blocksize $\beta$ ^[43] ※ Blocksize is the dimension of the sub-lattice the reduction algorithm tackles at each step. A larger blocksize means a stronger attack but exponentially more work, which is exactly the tradeoff parameter-setters exploit to fix a security level. , information-set decoding for codes, and Grover's quadratic speedup as the only quantum lever against a hash-based signature -- a speedup too shallow to matter at real parameter sizes ^[44]. None of these has broken a standardized parameter set. But "has not broken" is the operative phrase, and it cannot be upgraded to "cannot break" by any theorem we possess.

Standardized means survived the engine. It does not mean proven secure. A real proof of security for any of these schemes would imply $P \neq NP$ -- and more than that in the quantum setting -- so provably secure post-quantum cryptography is out of reach on principle today. Absence of a break is not a proof of security. It is the best evidence we can get, and it is not the same thing.

The bedrock results underneath do not close the gap either. Solving a generic system of multivariate quadratics is NP-hard; decoding a general linear code is NP-complete ^[45]. Those are worst-case statements, and the entire multivariate graveyard is the story of what happens when a scheme needs a trapdoor and therefore uses structured, non-worst-case instances. The NP-hardness of the general problem never protected the specific scheme.

The survivors are trusted not because anyone proved them secure, but because they are the ones nobody could break in time. Trust by attrition, not by proof.

If proof is impossible and the only evidence we have is "nobody has broken it yet," the natural next question is uncomfortable: is one of the survivors already living on borrowed time, the way Rainbow was in 2021?

9. Is any survivor next?#

The engine did not switch off when the standards published. It is still running, now aimed at the survivors -- and in April 2024 it briefly looked as if it had caught one.

That month, Yilei Chen posted "Quantum Algorithms for Lattice Problems," claiming a polynomial-time quantum algorithm for LWE ^[46]. If it held, it would have threatened ML-KEM and ML-DSA at once -- the KEM and the default signature, the majority of the entire migration, gone in a single paper. For a few days the lattice world held its breath. Then the engine did what the engine does. Within days, Hongxun Wu and, independently, Thomas Vidick found a fatal bug in the algorithm's Step 9, and Chen appended a note that the claim "does not hold" ^[46]. The Chen episode is the thesis in fast-forward. A claimed break of the survivors appeared, the community attacked it in the open, and the claim itself broke within days -- Wu and Vidick locating the flaw in Step 9. The same cheap, public, classical cryptanalysis that emptied the multivariate family now runs continuously over the schemes we standardized.

The same machine is visibly still emptying the multivariate family. Because the graveyard thinned the signature portfolio so badly, NIST opened an "additional signatures" on-ramp in 2023 ^[47]. Of its 40 first-round submissions, about 10 were broken within months ^[33]. The exact rectangular-MinRank weapon that finished Rainbow transferred straight to the key-compressed successors: the parameters of VOX fell to a padded-MinRank attack that broke eight of nine sets in under a minute ^[48], while MAYO, QR-UOV, and SNOVA saw parameter-weakening analyses. Plain, large-key UOV kept resisting. When NIST advanced 14 candidates to the on-ramp's second round in October 2024, the pattern from the first competition was repeating in miniature ^[49]. The "not never" is not a historical footnote. It is ongoing.

Two deeper questions hang over the survivors. The first is structural: SQIsign, the lone surviving isogeny signature, has to be made practical without reintroducing the kind of exposed structure that doomed SIDH -- and it comes from the very family that produced SIKE ^[40].

The second is the one that should keep architects awake: how correlated are the survivors' assumptions? ML-KEM and ML-DSA both rest on module-lattice hardness. A single structural idea -- a MinRank- or Kani-class surprise for lattices -- could in principle take both at once, and the portfolio's insurance is only as good as the independence of its bets. That forward-looking argument is the subject of this series' structural companion, "How the Whole Stack Would Break: SIDH, Correlated Assumptions, and the Cryptography We Are Betting the Next Thirty Years On"; this empirical capstone is the historical evidence that grounds it.

The pressure is not abstract, either. An adversary can record encrypted traffic today and decrypt it later if a break ever lands -- the "harvest now, decrypt later" problem -- so uncertainty about the survivors has a cost that is being paid right now, not someday ^[33]. None of this tells a practitioner to panic. It tells them to deploy as if the survivors might still fall -- which, it turns out, is a specific and achievable discipline.

10. What the graveyard tells you to do#

Everything above collapses into four rules a practitioner can act on this quarter.

Prefer the most-vetted families. For key exchange, ML-KEM; for signatures, ML-DSA by default and SLH-DSA where you want the most conservative assumption; Classic McEliece where keys are static and bandwidth is cheap. Treat "standardized" as "survived the engine" -- strong evidence, not a proof -- and you will hold these tools with the right amount of confidence.

Always hybridize. Deploy a classical and a post-quantum primitive together -- X25519 with ML-KEM, for instance -- so that breaking the post-quantum half does not break the session. SIKE is the empirical proof that this is not paranoia.

// A hybrid session key mixes BOTH shared secrets. Breaking one half is not enough.
function kdf(a, b) { // toy mixer (not a real KDF) -- only illustrates dependence on both inputs
let h = 2166136261 >>> 0;
for (const s of [a, b]) for (let i = 0; i < s.length; i++) { h ^= s.charCodeAt(i); h = Math.imul(h, 16777619) >>> 0; }
return h.toString(16).padStart(8, '0');
}

const ssClassical = 'x25519-shared-secret-stays-private';
const ssPq = 'sike-shared-secret';
const sessionKey = kdf(ssClassical, ssPq);
console.log('legitimate session key      :', sessionKey);

// 2022: SIKE is broken. The attacker recovers the post-quantum half in full...
const attackerPq = ssPq;
// ...but the classical half is still secret, so the attacker must guess it:
const attackerKey = kdf('attacker-cannot-see-x25519', attackerPq);
console.log('attacker key (PQ fully known):', attackerKey);
console.log('does the attacker recover the session?', attackerKey === sessionKey);

Never build on a pre-standardization candidate. Rainbow and SIKE were both live, respected candidates when they fell. A scheme that has not run the full gauntlet may break tomorrow, and anything you deployed on it breaks with it.

Track the status reports. NIST's status reports (NISTIR 8240, 8309, 8413, and 8545) and the signature on-ramp are the public record of what is still standing and what just fell ^[36]. Reading them is the cheapest security work you can do.

The root causes reduce to one lesson wearing five hats.

These four rules are really one rule wearing four hats: respect the difference between "unbroken" and "unbreakable." The graveyard is what that difference looks like when you ignore it.

11. Frequently asked questions#

The breaks generate a predictable set of misconceptions. Here are the seven worth settling.

Trust by attrition#

Count the funnel one last time. Eighty-two submissions became 69 first-round candidates, then 26, then 15, then a handful of standards. Two entire families -- multivariate signatures and isogeny key exchange -- did not merely lose members; they were emptied, on the mathematics itself, by ideas that a laptop could run in an afternoon. The schemes we now standardize are not the ones that were proven strong. They are the residue of everything that broke.

That is the shape of the only trust cryptography can actually offer. Across the rest of this series, the mathematics almost never broke and the machine around it leaked. This was the chapter where the mathematics broke -- not because cryptographers were careless, but because a competition deliberately ran young, unproven primitives at the entire world until the weak ones came apart in public, cheaply, before anyone was depending on them. Rainbow and SIKE were the price of admission, paid in papers instead of breaches.

The survivors earned the only credential the field can honestly grant: not a proof, but a record of having been attacked, in the open, by everyone who wanted to, and not yet having fallen. Hold them exactly that tightly -- and keep watching, because the engine that broke Rainbow the week it was a finalist has never stopped running.