# How the NIST Finalists Broke: Rainbow in a Weekend, SIKE in an Afternoon, and the Graveyard of Post-Quantum Candidates
> In 2022 two vetted NIST post-quantum candidates fell to classical math -- Rainbow in a weekend, SIKE in ten minutes. That is the process working, not failing.
*Published: 2026-07-19*
*Canonical: https://paragmali.com/blog/how-the-nist-finalists-broke-rainbow-in-a-weekend-sike-in-an*
*© Parag Mali. All rights reserved.*
---
Between February and August 2022, two vetted NIST post-quantum candidates were key-recovered on ordinary hardware by classical mathematics: **Rainbow**, an actual Round 3 signature finalist, in about 53 hours -- "a weekend" -- on a laptop; and **SIKE**, a key-exchange that had just advanced to Round 4, in about ten minutes on a single core, using a 1997 theorem that predates the scheme it destroyed. Neither fell to a quantum computer, an implementation bug, or a bad random number. The breaks hit the primitives' own algebra, and in both cases the exact feature that made the scheme competitive was the feature the attack exploited. That is not the competition failing. It is the competition working exactly as designed -- an industrial-scale, public cryptanalysis engine that runs unproven new primitives at the whole research community until the weak ones break cheaply, in the open, before anyone deploys them. The survivors we now standardize (ML-KEM, ML-DSA, SLH-DSA) earned their trust by attrition, not by proof -- and understanding that difference is the point of the whole story.
## 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 [@beullens-rainbow-2022-214]. 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 [@castryck-decru-2022-975].
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.
> **Key idea:** 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 [@nistir-8309]. 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 [@nistir-8413].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](/blog/how-q-day-breaks-everything-shors-algorithm-and-the-simultan/) [@shor-1994]. 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.
The two public-key roles the competition had to refill. A **KEM** lets two parties agree on a shared secret key over a public channel -- the job Diffie-Hellman and RSA key transport do today. A **digital signature** lets anyone verify that a message came from the holder of a private key, without revealing it. Rainbow was a candidate signature scheme; SIKE was a candidate KEM. Different jobs, different mathematics, both broken.
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.
A cryptographic building block whose security rests on a problem with no known efficient algorithm on either a classical or a quantum computer. "Post-quantum" is a claim about the *absence* of a known attack, not a proof of security -- a distinction that turns out to be the moral of the entire article.
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 [@nist-cfp-2016]. 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 [@nistir-8240]. 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 [@nist-aes-development, @nist-sha3-project]. 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.
The only kind of confidence a competition can actually produce: not a proof that a scheme is secure, but the accumulated observation that the entire research community, given years and strong incentives, failed to break it. Attrition yields *evidence* of hardness. It never yields *proof*. A scheme trusted by attrition is one that has been attacked in the open and has not yet fallen -- with the emphasis on "yet."
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 [@nistir-8240]. 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.
> **Note:** It is tempting to read a candidate's collapse as the competition catching a mistake. The sharper reading is that producing the collapse -- in public, on paper, before deployment -- is the competition's entire reason to exist. The engine's output is not the winner. Its output is every break that happened along the way, each one a bad primitive removed from the world's future at the cost of a research paper instead of a breach.
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 [@nistir-8240]. 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.
A multivariate signature scheme publishes, as its public key, a system of quadratic equations over a finite field that looks random. Solving a generic such system is believed hard -- the MQ problem is NP-hard in the worst case. The secret key is a hidden change of variables that splits the variables into "oil" and "vinegar" so that the system becomes easy to solve in one direction. The whole family lives or dies on one question: does the hidden structure that makes the trapdoor work leave a detectable fingerprint in the public key?
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 [@ks-ov-1998], which forced the unbalanced redesign published as UOV in 1999 [@uov-1999]; a separate big-field branch, Hidden Field Equations, had appeared in 1996 [@hfe-1996].
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 [@luov-2019-1490]. 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" [@gemss-hfev-2020-1424].
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 [@nistir-8309]. 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 [@rainbow-2005]. 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 [@beullens-2020-1343]. 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 [@beullens-rainbow-2022-214]. 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.
An **isogeny** is a structure-preserving map between two elliptic curves. In Supersingular Isogeny Diffie-Hellman (**SIDH**), proposed by David Jao and Luca De Feo in 2011 [@sidh-2011] and detailed in a 2014 journal version [@defeo-jao-plut-2014], each party's secret is a walk through a graph of supersingular curves, and the shared secret comes from combining the two walks. Its appeal was bandwidth: SIDH, packaged as the KEM named **SIKE**, had the smallest keys of any post-quantum key exchange in the competition [@sidh-2011, @round4-news-2022].
For SIDH to work, each party must publish not just the curve their secret walk ended on, but the *images* of certain public reference points (torsion points) under that secret walk. This auxiliary data is required for correctness -- the two parties cannot combine their walks without it. It is also, as of 2022, the exact information an attacker needs. The data the protocol must publish to function is the lever that breaks it.
On 5 July 2022, NIST selected its first four standards and advanced four KEMs -- including SIKE -- into a fourth round for continued study [@nistir-8413]. SIKE went in as an alternate, attractive for its small keys, never a finalist [@round4-news-2022].
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 [@castryck-decru-2022-975]. 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 [@kani-1997]. 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 [@maino-martindale-2022-1026]. 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 [@robert-2022-1038]. Eleven days, three papers, and an entire family of key exchange was finished.
> **Note:** Say it plainly, because the name misleads: no quantum computer was involved in breaking SIKE. The attack is classical mathematics running on ordinary hardware. A five-year warning even existed -- Christophe Petit had shown in 2017 that publishing torsion-point images makes isogeny problems easier to solve [@petit-2017-571]. And this attack targets SIDH, not CSIDH: the commutative isogeny scheme CSIDH does not publish torsion images, so Kani's lever does not reach it. SIDH fell; CSIDH still stands.
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 [@hertzbleed].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.
| Scheme | Competition standing | Break (primary source) | Cost / result | Mechanism |
|---|---|---|---|---|
| LUOV | Round 2 signature candidate | Ding et al., 2019 [@luov-2019-1490] | Below claimed NIST levels | Subfield attack on the "lifted" structure |
| GeMSS (HFEv-) | Round 3 alternate | Tao, Petzoldt, Ding, 2020 [@gemss-hfev-2020-1424] | "Not as secure as claimed" | Modifiers add little security |
| Rainbow | Round 3 **finalist** | Beullens, 2022 [@beullens-rainbow-2022-214] | Level-1 key in ~53 h on a laptop | Rectangular MinRank on layered Oil-and-Vinegar |
| MQDSS | Round 2 signature candidate | Eliminated per NISTIR 8309 [@nistir-8309] | Not advanced to Round 3 | Pressured (five-pass Fiat-Shamir) |
| qTESLA | Round 2 signature candidate | Eliminated per NISTIR 8309 [@nistir-8309] | Not advanced to Round 3 | Superseded by Dilithium and Falcon |
| SIKE | Round 3 alternate to Round 4 | Castryck, Decru, 2022 [@castryck-decru-2022-975] | SIKEp434 key in ~10 min on one core | Kani's criterion on published torsion images |
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.
Given a collection of matrices, find a linear combination of them that has rank at most some small target $r$. MinRank is NP-hard in general, but for a scheme whose secret *plants* a low-rank combination, the problem is not generic -- the structure is there to be found. Recovering a multivariate trapdoor repeatedly reduces to MinRank, which is why cryptographers call it the family's recurring weapon.
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 [@beullens-2020-1343, @beullens-rainbow-2022-214]. 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 [@ks-hfe-relin-1999]. 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.
A 1997 theorem in the arithmetic of abelian surfaces that tells you when an abelian surface (a two-dimensional abelian variety) splits as a product of elliptic curves. The attack builds an auxiliary isogeny in dimension two (later, higher dimensions) out of SIDH's published torsion images, then uses Kani's criterion as a yes/no test: does this object split? A "yes" confirms a guessed piece of the secret isogeny, so the criterion becomes an oracle that reconstructs the secret walk one step at a time.
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 [@robert-2022-1038]. 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 [@petit-2017-571].
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.
> **Key idea:** 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 [@nist-press-2024]. 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) [@fips-203], the key-encapsulation mechanism derived from CRYSTALS-Kyber [@pqcrystals-kyber], is the lattice workhorse: keys and ciphertexts of roughly one kilobyte, fast enough to be a near drop-in for [elliptic-curve key agreement](/blog/how-elliptic-curves-and-diffie-hellman-break-in-real-life-th/). **ML-DSA** (FIPS 204) [@fips-204], from CRYSTALS-Dilithium [@pqcrystals-dilithium], is the default signature, chosen for a balance of size, speed, and implementation safety.
**[SLH-DSA](/blog/how-slh-dsa-would-break-the-signature-that-can-only-fall-if-/)** (FIPS 205) [@fips-205], from SPHINCS+ [@sphincs-org], 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](/blog/how-falcon-would-break-ntru-lattices-and-the-structure-nobod/)), 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 [@cloudflare-pq-2024].
NIST rates each parameter set against a familiar yardstick rather than an absolute bit count. Category 1 means "at least as hard to break as recovering an AES-128 key by exhaustive search"; category 3 pegs to AES-192; category 5 to AES-256. Categories 2 and 4 peg to the difficulty of finding a SHA collision. This lets wildly different mathematics -- lattices, codes, hashes -- be compared on one scale.
The assumption under both ML-KEM and ML-DSA. Given a public matrix $A$ over a polynomial ring and a value $b = A s + e$, where the secret $s$ and the noise $e$ are small, recovering $s$ is believed hard. "Module" refers to the algebraic structure that makes the scheme efficient -- and, as we will see, is also the structure whose security is not fully covered by the field's best hardness theorems.
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 [@classic-mceliece-org], and its one-way encryption is turned into a modern key-encapsulation mechanism by a tight security reduction [@kem-unification-2018-526]. 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 [@nistir-8545].
Its structural cousin **HQC**, based on decoding quasi-cyclic codes, was selected in March 2025 as the fifth standard [@hqc-news-2025].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.
| Survivor | Family | Role | Sizes (approx) | Assumption maturity | NIST status |
|---|---|---|---|---|---|
| ML-KEM (FIPS 203) | Lattice (Module-LWE) | KEM | keys and ciphertext ~0.8 to 1.6 KB | High (most-attacked young assumption) | Final, Aug 2024 |
| ML-DSA (FIPS 204) | Lattice (Module-LWE + SIS) | Signature | pk 1.3 to 2.6 KB, sig 2.4 to 4.6 KB | High | Final, Aug 2024 |
| FN-DSA / Falcon | Lattice (NTRU) | Signature | sig ~0.7 to 1.3 KB (smallest) | High | Draft FIPS 206 (delayed) |
| SLH-DSA (FIPS 205) | Hash | Signature | pk 32 to 64 B, sig ~8 to 49 KB | Highest (hash-only) | Final, Aug 2024 |
| Classic McEliece | Code (binary Goppa) | KEM | pk 261 KB to 1.36 MB, ct ~0.1 to 0.2 KB | Highest (since 1978) | Deferred to ISO |
| HQC | Code (quasi-cyclic) | KEM | pk ~2.2 KB, ct ~4.5 KB | Medium | Selected 2025, draft |
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 [@cloudflare-pq-2024].
> **Note:** The survivors have been hit, but not on their mathematics. Timing and fault side channels with names like KyberSlash have leaked secrets from specific ML-KEM implementations [@cloudflare-pq-2024]. Those are exactly the "the machine leaked" failures the rest of this series covers -- the companion piece "How ML-KEM Breaks in Real Life" is their proper home. They do not touch the Module-LWE assumption itself, and this article is strictly about breaks of the mathematics.
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 [@classic-mceliece-org].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 [@mceliece-1978]. 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 [@csidh-2018-383]. **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 [@sqisign-2020-1240]. 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 [@mayo-2021-1144]. The clever descendants died. The conservative ancestors lived.
| Family | Hard problem | Optimized for | Outcome in the competition |
|---|---|---|---|
| Lattices | Module-LWE / NTRU | Balance of size and speed | Survived: ML-KEM, ML-DSA, Falcon |
| Codes | Syndrome decoding | Decades of stability | Survived: Classic McEliece (ISO), HQC |
| Hashes | Hash preimage resistance | Minimal assumptions | Survived: SLH-DSA |
| Multivariate | Structured MQ trapdoors | Small keys and signatures | Near-extinct: Rainbow, GeMSS, LUOV dead |
| Isogenies | Supersingular isogeny walk | Smallest keys | KEM line dead (SIKE); CSIDH, SQIsign live |
The Round 3 record makes the diversification argument concrete. When Rainbow and SIKE were named finalist and alternate respectively, they were live bets [@nistir-8309]. When they broke, the standard did not break with them, because the other bets were still there [@nistir-8413]. 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 [@langlois-stehle-2012-090]. 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."
A proof that breaking a *randomly chosen* instance of a problem is at least as hard as solving the *hardest* instance of a related problem. It matters because cryptography needs random keys to be hard, not just some cherry-picked key. Lattices have such a reduction; codes and multivariate schemes do not, which is part of why the multivariate family's structured instances turned out to be so much weaker than the worst case suggested.
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$ [@bdgl-2015-1128]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 [@grover-1996]. 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.
> **Key idea:** 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 [@syndrome-decoding-1978]. 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 [@chen-2024-555]. If it held, it would have threatened [ML-KEM and ML-DSA](/blog/two-standards-one-lattice-how-ml-kem-and-ml-dsa-would-break/) 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" [@chen-2024-555].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.
> **Note:** It is a mistake to read the Chen scare as a near-miss that we got lucky on. The right reading is that the machine worked exactly as designed, one more time: no claim about these primitives -- for or against -- goes unchecked for long. That is the only thing standing between "we trust ML-KEM" and "we were wrong about ML-KEM," and it never stops.
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 [@nist-addsig-call]. Of its 40 first-round submissions, about 10 were broken within months [@cloudflare-pq-2024]. 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 [@vox-2024-166], 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 [@digsig-round2-news-2024]. 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 [@sqisign-2020-1240].
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](/blog/q-day-has-not-happened-the-incident-already-has-harvest-now-/) 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 [@cloudflare-pq-2024]. 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.
> **Note:** The single most expensive mistake the graveyard warns against is treating "advanced to the next round" as "safe to deploy." Rainbow was a finalist and SIKE a Round 4 candidate at the moment each was key-recovered. Pre-standardization status is an invitation to attack a scheme, not a certificate that it survived.
**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 [@nistir-8545]. Reading them is the cheapest security work you can do.
Recent browsers negotiate a hybrid key-exchange group named X25519MLKEM768 (earlier builds used X25519Kyber768) [@cloudflare-pq-2024]. In Chrome or Firefox, open the connection or security details panel and look at the negotiated key-exchange group; a current build of OpenSSL's `s_client` also reports the negotiated group in its handshake summary. If you see an ML-KEM or Kyber hybrid, both the classical and the post-quantum halves are protecting that session -- exactly the arrangement that saved CECPQ2b.
| If you need | Use | Trust basis | Hybrid? |
|---|---|---|---|
| TLS / key agreement | ML-KEM-768, in an X25519+ML-KEM hybrid | most-studied young assumption | Yes, always |
| A code-based KEM hedge | HQC (when final) or Classic McEliece (static keys) | distinct from lattices | Yes |
| Default signature | ML-DSA-65 | balanced, implementation-safe | with a classical signature where feasible |
| Smallest signatures (CA roots) | FN-DSA / Falcon (after FIPS 206) | small, but sampling hazard | Yes |
| Maximum assurance / firmware | SLH-DSA | hash-only, most conservative | optional |
| Anything pre-standardization | do not build on it | none -- may break tomorrow | not applicable |
The root causes reduce to one lesson wearing five hats.
| Broken scheme | Root-cause mathematics | Lesson |
|---|---|---|
| Rainbow | Layering created a low-rank MinRank instance [@beullens-rainbow-2022-214] | Key-shrinking structure is attack structure |
| GeMSS / HFEv- | Modifiers added little real security [@gemss-hfev-2020-1424] | Patching a weak trapdoor does not strengthen it |
| LUOV | Lifted structure reduced to a subfield [@luov-2019-1490] | Efficiency tricks can shrink the attacker's search |
| SIKE | Published torsion images fed Kani's criterion [@castryck-decru-2022-975] | Data you must publish is data an attacker has |
| VOX (on-ramp) | Padded MinRank on compressed UOV keys [@vox-2024-166] | The same weapon still fires today |
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.
No. Both were broken while they were candidates in a standardization process, before any general deployment, so there is no CVE and no vendor advisory for either. The one real-world appearance was SIKE inside the time-boxed CECPQ2b experiment, which paired it with X25519 -- and even there, the break did not exploit the deployment, and the sessions stayed secure because the classical half held [@cloudflare-pq-2024].
No. The break is classical mathematics -- Kani's 1997 reducibility criterion applied to the torsion-point images SIDH publishes -- and Robert showed it runs in classical polynomial time [@castryck-decru-2022-975, @robert-2022-1038]. Shor's algorithm was not involved. Note also that this attack hits SIDH, not the commutative scheme CSIDH, which does not publish torsion images.
The opposite. Cheap, public, classical cryptanalysis of candidates -- before anyone deploys them -- is the entire point of an open competition. Rainbow and SIKE breaking on paper is the process working exactly as designed, not failing. A competition that produced no breaks would be the worrying outcome.
No. They are trusted by attrition, not by proof. No one has proved Module-LWE or syndrome decoding hard; a real proof would imply $P \neq NP$ and more in the quantum setting. Absence of a known break is the best evidence available, and it is not the same as a guarantee.
The families were pruned, not eliminated. The specific submitted schemes -- Rainbow, GeMSS, LUOV, and SIDH/SIKE -- are dead. But plain Unbalanced Oil-and-Vinegar and its revival MAYO resist the MinRank attack [@mayo-2021-1144], and the isogeny schemes CSIDH and SQIsign survive because they do not expose the torsion images that doomed SIDH [@csidh-2018-383, @sqisign-2020-1240].
The cryptanalytic engine still runs on the survivors, and no one can rule it out. In 2024 a claimed quantum algorithm against LWE briefly threatened both, then self-destructed within days when a bug was found [@chen-2024-555]. No working break is known today -- but "no known break" is evidence, not a promise.
Four things: prefer the most-vetted families (lattice, hash, and Classic McEliece); always hybridize a classical primitive with the post-quantum one so a future break cannot expose today's traffic; track NIST's status reports and the signature on-ramp; and never build on a pre-standardization candidate [@cloudflare-pq-2024, @nistir-8545].
## 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.