How the Whole Stack Would Break: SIDH, Correlated Assumptions, and the Cryptography We Are Betting the Next Thirty Years On
No post-quantum algorithm is proven hard. The stack's only real defense is a deliberately uncorrelated portfolio of lattice, code, and hash assumptions.
Permalink1. Nine Teardowns, One Question
In late July 2022, a key-exchange scheme that had survived eleven years of public cryptanalysis was broken. Not by a quantum computer. Not gradually. It fell on a single laptop core in about ten minutes, using a theorem from pure mathematics published in 1997 [1]. The scheme was SIKE, the instantiation of SIDH first proposed in 2011 [2], and just three and a half weeks earlier NIST had promoted it to the fourth and final round of its post-quantum standardization effort for continued study [3].
Read the status carefully, because the precise words carry the whole point. SIKE was never a standard. It was a Round-4 alternate candidate, still under evaluation, key-recovered before any selection was made [4]. That makes the collapse worse, not better: this was cryptography failing while under the most intense scrutiny our field knows how to apply.
This series has spent nine articles taking post-quantum primitives apart one at a time: how ML-KEM would break, how ML-DSA would break, how each candidate meets its mathematical limit. This final part does what none of the nine could do alone: it steps back and asks whether they fail independently. Because a stack is not nine separate bets that each has to be strong. It is one system, and its real question is whether two of those bets might secretly be the same bet.
A cryptosystem is a wager that one math problem is hard. A cryptographic stack is a portfolio of such wagers -- and the only thing that ultimately matters is whether the wagers are correlated. The stack is secure not because any assumption is proven hard (none is), but only to the degree that a break of one leaves the others standing.
That is the lens for everything below -- a sentence you will earn by the end.
A cryptographic stack is a portfolio of bets -- and the only thing that ultimately matters is whether the bets are correlated.
Before we map the stack, one boundary. The break we just described was structural: an attack on SIDH's own mathematics, not on a buggy implementation of it. SIDH is not CSIDH. SIDH collapsed classically in 2022; CSIDH is a separate isogeny construction that survives, with its own separately-contested quantum security -- Kuperberg's algorithm applies to CSIDH, never to lattices [5]. Never let one family's obituary be read as the other's. That distinction is the boundary every section below holds to.
The thirty-year story we are about to trace is a spiral, not a line. Three times the field concentrated its security onto one kind of mathematics, and three times a shock forced it to spread out again.
Diagram source
flowchart LR
A["1978 McEliece: the first code-based bet"] --> B["1994 Shor: two bets share one spine"]
B --> C["2005 LWE: the lattice core arrives"]
C --> D["2016 NIST competition: five families enter"]
D --> E["2022 SIDH collapses, classically"]
E --> F["2024 FIPS 203, 204, 205 published"]
F --> G["2025 HQC selected as the code hedge"] To answer whether the new bets are correlated, we first have to understand the last time they were -- the one moment when a single idea took the entire classical stack at once.
2. Shor: The Original Correlated Failure
For twenty years the field slept soundly because breaking RSA seemed to say nothing about breaking elliptic-curve cryptography. That comfort was an illusion -- the most important one to understand here, because the entire post-quantum project is an attempt not to fall for it twice.
The numbers told a reassuring story. The best classical attack on RSA was the general number field sieve, with a sub-exponential running time; the best classical attack on elliptic curves was Pollard's rho, a square-root method [6]. Two problems, two unrelated algorithms, two independent-looking bets. If someone found a faster way to factor, elliptic curves would be untouched, and vice versa. Diversify across both and you were doubly safe -- or so the reasoning went.
The foundation of all public-key cryptography: security rests on the belief that some specific problem -- factoring a 2048-bit number, recovering a short lattice vector -- is too expensive to solve on average, for anyone, with any known method. The operative word is belief. "Nobody has broken it yet" is evidence, not a proof; almost nothing in cryptography is proven hard.
Then, in 1994, Peter Shor showed that both bets were the same bet. His polynomial-time quantum algorithm solved integer factoring and discrete logarithm, because underneath their different surfaces both are instances of a single mathematical object: the abelian hidden-subgroup problem [7]. Find the hidden periodic structure and you have solved the factoring instance, the discrete-log instance, and the elliptic-curve instance alike.
Diagram source
flowchart TD
RSA["RSA: integer factoring"] --> HSP{"Abelian hidden-subgroup problem"}
ECC["ECC: discrete logarithm"] --> HSP
HSP --> SHOR["Shor, 1994: polynomial-time quantum HSP"]
SHOR --> Z1["RSA falls"]
SHOR --> Z2["ECC falls"] This is the template for everything this article fears. Two primitives can each be individually strong -- decades of failed attacks, careful parameter choices, universal deployment -- and still fall together, in one stroke, because their strength was never really two separate things.
Two honest caveats keep this precise. First, Shor's algorithm needs a large, fault-tolerant quantum computer that does not yet exist; its threat is future, not present, and it does not threaten any of the lattice, code, or hash schemes we will meet below. Grover's algorithm is the other quantum result people cite. It gives only a generic quadratic, , speedup for unstructured search -- effectively halving a symmetric key's strength, so a 256-bit key still offers about 128 bits against a quantum attacker [8]. That is absorbed by larger parameters, not a structural break, and the last we will say of it. Second, the reason Shor matters here is historical, not technical: it is the event that created the field. The looming "Q-Day," when a quantum computer runs Shor at scale, is precisely the correlated failure that made everyone go looking for replacements.
If the lesson of Shor is that independent-looking bets can share a hidden spine, then the obvious first move after 1994 -- just swap RSA and elliptic curves for one quantum-safe algorithm -- walks straight back into the same trap.
3. The Naive Swap Rebuilt the Single Point of Failure
The first instinct after Shor was the worst one: treat it as a component swap. Rip out RSA and elliptic curves, find one quantum-safe replacement, and declare victory. The instinct is understandable -- engineers replace broken parts every day -- but it is exactly the mistake the correlation lens tells you to avoid.
The raw material was already on the shelf. The candidate problems with no exploitable abelian-HSP structure had existed for decades: McEliece's code-based cryptosystem from 1978 [9], Merkle's hash-based signatures from 1979 [10], the NTRU lattice system from 1998 [11], and Regev's Learning With Errors problem from 2005, which would become the workhorse of the entire modern stack [12]. Any of them could resist Shor. The temptation was to pick the most efficient one and standardize it alone.
A deployed stack whose security, however many algorithms it contains, ultimately rests on a single hard-problem family. Like a field planted with one genetic strain, it can look healthy right up until a single blight -- one mathematical advance -- takes all of it at once.
Here is why a single replacement is not a fix but a relocation of the risk. Shor did not punish RSA for being weak; it punished the stack for concentrating on one kind of mathematics. Swap in a lone lattice scheme and you have rebuilt precisely that: a monoculture with a new problem underneath, one advance away from total failure. You did not escape the Shor pattern. You reissued it.
To be honest about the epistemics: no paper proves the theorem "monocultures always fail." This is a design argument, and its evidence is circumstantial rather than deductive -- the Shor precedent behind us, and, as we will see, the collapses of SIKE and Rainbow still ahead.
The people who saw it earliest said so in plain terms. Daniel Bernstein and Tanja Lange argued for years that committing to a single system courts a "cryptographic monoculture," and built NTRU Prime partly as a standing objection to it [13]. That position, once a minority view, is the intellectual seed of everything NIST eventually did.
Because NIST did not swap. It ran a competition.
NIST bet on breadth -- five families, an open process, trust earned by attrition. But breadth on paper is not diversity in fact. A competition can start with five families and still funnel almost all of its real-world weight onto one of them. To see whether that happened, you have to stop reading the roster and start reading the map -- exactly what the survivors ended up standing on.
4. The Map of What Rests on What
Here is the uncomfortable picture, drawn as a map. Take the standardized and selected post-quantum stack, ignore the marketing names, and color each scheme by the hard problem it actually rests on. Where is the concentration?
The modern public-key primitive for agreeing on a shared secret. Rather than encrypting a chosen message, the sender encapsulates a fresh random key against the recipient's public key, producing a ciphertext; the recipient decapsulates it to recover the same key. ML-KEM, HQC, and Classic McEliece are all KEMs.
Six schemes carry the weight. ML-KEM (FIPS 203) is a lattice KEM whose security is tied to Module-LWE at modulus q = 3329 [16]. ML-DSA (FIPS 204) is a lattice signature resting on Module-LWE and Module-SIS at modulus q = 8380417 [17]. Falcon (draft FIPS 206) is a lattice signature too, but on the NTRU short-vector problem rather than Module-LWE [11].
SLH-DSA (FIPS 205) is a signature whose security reduces entirely to the strength of a hash function [18]. Classic McEliece rests on decoding random binary Goppa codes [9], and HQC -- selected by NIST in March 2025 -- rests on decoding quasi-cyclic codes [19].
Diagram source
flowchart TD
subgraph Lattice
MLKEM["ML-KEM on Module-LWE"]
MLDSA["ML-DSA on Module-LWE plus Module-SIS"]
FAL["Falcon on the NTRU lattice"]
end
subgraph Hash
SLH["SLH-DSA on hash security only"]
end
subgraph Code
HQC["HQC on quasi-cyclic decoding"]
MCE["Classic McEliece on binary-Goppa decoding"]
end
MLKEM -.->|shared Module LWE assumption| MLDSA The hard problem underneath both ML-KEM and ML-DSA. Informally it is noisy linear algebra over structured (module) lattices: you are shown many linear equations whose right-hand sides have each been nudged by a small random error, and asked to recover the secret. "Module" is the middle setting between fully unstructured LWE (slow but conservative) and fully structured Ring-LWE (fast but more algebraic surface for an attacker to grab).
The map makes one fact impossible to miss: three of the six schemes stand on lattices. That concentration is not an accident. It is the payoff of a twenty-year efficiency arc -- Ajtai's 1996 worst-case-to-average-case reduction [20], Regev's LWE in 2005 [12], Ring-LWE's dramatic size reductions in 2010 [21], and the Module-LWE middle ground in 2015 [22] that Kyber and Dilithium adopted in 2017 to become today's ML-KEM and ML-DSA [23, 24]. Lattices won the efficiency argument, and that is why they became the core.
But notice the precise shape of the correlation, because misstating it is the single most common error about this stack. ML-KEM and ML-DSA are the genuinely correlated pair: both rest on Module-LWE. That does not mean any attack on one instantly breaks the other. They use different parameters -- different moduli (3329 versus 8380417), different module ranks, The rank is roughly how many ring elements stack into the secret vector; a higher rank means a harder instance and a larger key. different noise -- so a parameter-specific attack need not transfer, and ML-DSA carries an additional Module-SIS assumption that ML-KEM does not [17].
You can turn that observation into a two-line audit. Do not count algorithms; count assumptions.
// Map each deployed scheme to the hard problem it truly rests on.
const assumption = {
'ML-KEM-768': 'lattice',
'ML-DSA-65': 'lattice',
'Falcon-512': 'lattice',
'SLH-DSA-128s': 'hash',
'HQC-128': 'code',
'Classic-McEliece': 'code'
};
// A stack is only as diverse as its set of DISTINCT assumptions.
function auditStack(schemes) {
const families = new Set(schemes.map(function (s) { return assumption[s]; }));
console.log('Deployed: ' + schemes.join(', '));
console.log('Distinct assumption families: ' + Array.from(families).join(', '));
if (families.size === 1) {
console.log('WARNING: monoculture. One advance against ' +
Array.from(families)[0] + ' takes the whole stack.');
} else {
console.log('OK: a break must cross ' + families.size +
' unrelated families to take everything.');
}
}
auditStack(['ML-KEM-768', 'ML-DSA-65', 'Falcon-512']); // looks diverse, is not
auditStack(['ML-KEM-768', 'SLH-DSA-128s', 'HQC-128']); // lattice + hash + code Press Run to execute.
The first stack has three different algorithm names and one assumption. The second has three names and three assumptions. Only the second is a portfolio.
The map is the thesis. Every scheme sits in exactly one assumption band -- lattice, hash, or code -- and every break lives in a band too. To take the whole stack down, a single break would have to cross bands, reaching mathematics unrelated to where it started. Diversity is not decoration on top of the security argument. It is the security argument.
The map, laid out precisely, and the five generations of thinking that produced it:
| Scheme (standard) | Role | Family | Specific assumption | Best-known attack | Representative size | Correlation group |
|---|---|---|---|---|---|---|
| ML-KEM (FIPS 203) | KEM workhorse | Lattice | Module-LWE, q = 3329 | Lattice sieving / BKZ [25] | ~1 KB public key | Lattice core |
| ML-DSA (FIPS 204) | Signature workhorse | Lattice | Module-LWE + Module-SIS, q = 8380417 | Lattice sieving / BKZ [25] | ~3 KB signature | Lattice core (paired) |
| Falcon (draft FIPS 206) | Compact signature | Lattice | NTRU short vector | Lattice sieving / BKZ [25] | sub-kilobyte signature | Lattice (distinct) |
| SLH-DSA (FIPS 205) | Conservative signature | Hash | Hash preimage / collision resistance | Generic hash attacks | several to tens of KB signature | Hash anchor (uncorrelated) |
| HQC (NIST IR 8545) | KEM hedge | Code | Quasi-cyclic syndrome decoding | Information-set decoding [26] | few-KB public key | Code hedge |
| Classic McEliece (ISO-track) [27] | KEM deep hedge | Code | Binary-Goppa syndrome decoding | Information-set decoding [26] | 0.26-1.36 MB public key [28] | Code hedge |
| Generation | Era | What we bet on | How we avoided concentrating | Why it was superseded |
|---|---|---|---|---|
| Number-theoretic monoculture | pre-1994 | Factoring and discrete log (RSA, ECC) | We did not -- two problems were believed independent | Shor: both are one abelian-HSP bet [7] |
| Naive one-for-one swap | 1994-2016 | A single quantum-safe replacement | Not at all -- one new problem underneath | Rebuilds the monoculture Shor punished |
| Five-family bake-off | 2016-2022 | An open competition across five families | Breadth of candidates [14] | Attrition thinned it toward a lattice-heavy core |
| Lattice-centric core | 2022-2024 | Module-LWE efficiency (ML-KEM, ML-DSA) | Partly -- hash-based SLH-DSA retained | Concentration risk: three lattice schemes |
| Diversified portfolio | 2024-2025 | Lattice, hash, and code, explicitly | Dated policy: SLH-DSA, then HQC [19] | Current -- the correction made explicit |
A map like this is only a worry until a family actually vanishes from it. That is not hypothetical. An entire family that reached NIST's Round-4 shortlist -- isogenies -- did exactly that, while sitting under the most intense scrutiny the field can muster.
5. SIDH: How a Family Vanished in an Afternoon
Return to the ten-minute break and look at exactly how it worked, because the mechanism is the warning. A scheme that survived more than a decade did not fall to a new theory, a faster computer, or a lucky guess. It fell to arithmetic that had been sitting in a 1997 journal, waiting.
SIDH's hard problem is to find a secret isogeny -- a structured map -- between two supersingular elliptic curves. That problem, taken bare, still looks hard today. But a protocol has to do more than pose a hard problem; it has to let two honest parties reach the same key. To make that possible, SIDH publishes extra data alongside its public key: the images of certain torsion points under the secret isogeny [2]. That auxiliary information is not part of the underlying hard problem. It is a gift the protocol hands the attacker in order to function.
An isogeny is a structure-preserving map between two elliptic curves. SIDH hides its secret in a specific isogeny and dares attackers to find it. But to let two parties agree on a key, the protocol must also publish the images of certain torsion points under that secret map. Those published images are auxiliary data the bare hard problem never had to reveal -- and they are exactly what the attack fed on.
In late July 2022, Wouter Castryck and Thomas Decru showed how to weaponize that gift. They applied Kani's reducibility criterion -- a result in arithmetic geometry published in 1997 and essentially unused in cryptography for twenty-five years [29] -- to the published torsion-point images. The criterion lets you glue the curves into a higher-dimensional abelian surface and test whether it splits, and from that test recover the secret isogeny. On SIKEp434 it ran in about ten minutes on a single classical core [1].
Diagram source
sequenceDiagram
participant P as Protocol
participant A as Attacker
P->>A: Publishes torsion-point images (required to function)
A->>A: Apply Kani reducibility criterion from 1997
A->>A: Glue curves into an abelian surface, test reducibility
A->>P: Recover the secret isogeny (the private key)
Note over A: About ten minutes, one core, classical, not quantum It was not a fluke of one parameter set. Within weeks, Damien Robert proved the attack runs in classical polynomial time from any starting curve, sealing the result as structural rather than patchable [30], and Luciano Maino and Chloe Martindale generalized it while carefully bounding it away from neighboring constructions [31].
Now sit with the three facts that make this the emotional center of the article. It was not Shor and not a quantum computer -- an ordinary laptop did it. The interval is the whole point. SIKE advanced to Round 4 on 5 July 2022 and was broken around 30 July 2022 -- roughly three and a half weeks later [3, 1]. Years of survival bought time, not safety. It was not gradual erosion -- one paper took the family from "final round" to "dead." And the vulnerability was structural from birth: SIDH published its own attack surface on day one, and the tool that read it had existed, fully public, since 1997.
Here is the shift. Most of us treat heavy vetting as evidence of durability: if a scheme survives years of expert attack, surely it is safe. SIKE says otherwise. Vetting measures how long a family has resisted the tools people thought to try. It cannot measure the tool nobody connected yet -- and that tool can already be published, in a field the cryptographers were not reading.
The mathematics that collapses a quantum-safe family can already exist, fully published, decades before anyone connects it to the target.
If a whole family can vanish like this -- classically, in an afternoon, at the peak of its scrutiny -- then the only rational response is to never bet the stack on one. That is precisely, and deliberately, what NIST built next.
6. The Portfolio NIST Actually Built
The standardized stack is not a winner. It is a portfolio, and it was designed rather than stumbled into. Read across the three families and you can see the strategy in the shape.
The lattice pair, ML-KEM and ML-DSA, are the efficient workhorses -- small keys, fast operations, the default choice for general traffic [16, 17]. Next to them sits the maximally conservative anchor: SLH-DSA, a signature whose security reduces entirely to the strength of a hash function and shares no algebraic structure with lattices at all [18]. Its lineage runs straight back to the SPHINCS stateless hash-based signature of 2015 [32]. If every lattice assumption on the map fell tomorrow, SLH-DSA would not notice.
The hard problem behind code-based cryptography. Given a random-looking linear code and a corrupted codeword, recover the small error pattern that was added. That recovery is a decoding problem which has resisted efficient solution since the 1970s. HQC and Classic McEliece both rest on variants of it.
The third family is the encryption hedge. Classic McEliece has stood essentially unbroken as a structure for roughly 47 years, the deepest-studied bet on the board [28]. McEliece's conservatism has a price: its public keys run from about 0.26 MB to 1.36 MB depending on parameters [28], roughly two to three orders of magnitude larger than ML-KEM's. That bandwidth is the price of a structure unbroken for nearly half a century. And in March 2025, NIST added HQC, a newer code-based KEM built on quasi-cyclic codes [33], precisely to have a standardized encryption path that does not touch lattices.
That selection is the thesis rendered as a signed, dated decision. A monoculture-minded process would have shipped one KEM -- the fastest -- and moved on. NIST shipped a second one on a different hard problem, and said out loud that non-correlation was the reason.
NIST did not choose HQC because it was the fastest or the smallest. It chose HQC because it is not a lattice.
Here is the whole portfolio as an engineering comparison. The last row -- correlation to the lattice core -- is the one this article cares about most.
| Dimension | Lattice core (ML-KEM / ML-DSA) | Lattice (Falcon) | Hash (SLH-DSA) | Code (HQC) | Code (McEliece) |
|---|---|---|---|---|---|
| Worst-case structural threat | Generic Module-LWE advance | Advance on NTRU lattices | Break of the underlying hash | ISD advance on quasi-cyclic codes | ISD advance on Goppa codes |
| Best-known attack cost | Sieving [25] | Sieving [25] | Generic hash bounds | ISD [26] | ISD [26] |
| Representative size | ~1 KB pk, ~3 KB sig | sub-KB signature | KB-scale signature | few-KB public key | 0.26-1.36 MB public key [28] |
| Performance | Fast | Compact, fast verify | Slower, larger signatures | Moderate | Fast operations, very large keys |
| Attack-cost verifiability | Contested margin [28] | Contested margin | High (hash-based) | Machine-checkable | Machine-checkable, most stable |
| Correlation to lattice core | It is the core | High (lattice) | None (hash) | Low (code) | Low (code) |
A portfolio on paper only becomes a defense when it is fielded, and this one is. On the wire, the dominant deployment is a hybrid: a classical key exchange and a lattice KEM run together, most commonly the X25519MLKEM768 group, which pairs X25519 with ML-KEM-768, the two primitives it shares with the general-purpose X-Wing combiner [34].
Running a classical key exchange (say X25519) and a post-quantum KEM (say ML-KEM) side by side, then combining their two shared secrets through a key-derivation function. The result is secure as long as either half is unbroken, so a surprise break of the post-quantum piece does not, on its own, expose the session.
The adoption is real and recent. By early 2024, roughly 2 percent of TLS 1.3 connections to Cloudflare used post-quantum key exchange, with over 99 percent of that traffic driven by Chrome [35]. Apple's iMessage PQ3 and Signal's PQXDH shipped post-quantum protection into production messaging [36, 37]. And the NSA's CNSA 2.0 suite mandates ML-KEM and ML-DSA, plus the stateful hash-based signatures LMS and XMSS for software- and firmware-signing, for national security systems on a timeline running to 2033 [38]. The portfolio is not a whiteboard proposal; it is being poured into the foundations of the internet right now.
A portfolio is only a defense, though, if its bets are genuinely uncorrelated. So the honest question -- the one that separates comfort from security -- is whether these bets are independent. They are not all as independent as the map makes them look.
7. Are the Bets Actually Uncorrelated?
This is where the map earns its keep. Press on each band and watch how far the crack spreads. There are three verdicts to reach and one uncomfortable caveat that undercuts all of them.
The caveats from Section 4 still hold and still matter -- Falcon is NTRU rather than Module-LWE, the parameters differ, and ML-DSA carries an extra Module-SIS route -- so not every lattice result hits all three. But the honest summary is stark: the single most valuable target on the board is "lattices in general," and three standardized schemes sit behind it.
Diagram source
flowchart TD
GEN["Generic Module-LWE break"] --> MLKEM["ML-KEM"]
GEN --> MLDSA["ML-DSA"]
LR["Large lattice-reduction advance"] --> MLKEM
LR --> MLDSA
LR --> FAL["Falcon"]
ISD["Information-set decoding advance"] --> HQC["HQC"]
ISD --> MCE["Classic McEliece"]
HASH["Hash function break"] --> SLH["SLH-DSA"]
NN["Nearest-neighbor search"] -.-> LR
NN -.-> ISD The best-known family of attacks against code-based cryptography. ISD guesses a subset of coordinates it hopes are error-free, solves the resulting linear system, and checks whether the implied error is small enough, repeating until it succeeds. Fifty years of refinement have chipped at its exponent without changing its exponential character -- which is exactly why the code margin is considered stable.
The hash anchor is the least correlated bet on the map, but not perfectly isolated. SLH-DSA shares no algebraic structure with lattices or codes at all; its only correlation is to the strength of the SHA-2 and SHA-3 families it is built on. And those carry the largest, most-attacked security margins in all of cryptography. If you wanted the closest thing to an assumption that fails for reasons entirely its own, this is it. The lattice margin, by contrast, is not settled. Concrete-security estimates that NIST itself has published for Kyber-512 have spanned roughly to gates depending on modeling assumptions [28]; the code margin is comparatively stable and can be checked by attack-cost simulators.
Now the caveat that keeps this section honest. Lattice sieving and code-based ISD, at their algorithmic cores, both reduce to the same primitive: finding very close vectors in a huge set, a nearest-neighbor search. The best sieving algorithms and the best decoding algorithms have both been sharpened by advances in nearest-neighbor techniques [25]. So it is conceivable that one deep breakthrough in nearest-neighbor search could sharpen attacks in both the lattice band and the code band at once -- a meta-correlation the tidy three-color map hides.
I have to mark that claim precisely, because overstating it would betray the whole argument. No published result demonstrates an attack that transfers between the families, and no reduction is known in either direction. This is an inferred caution, not a documented failure.
So the encryption diversity is real but not proven, and the lattice concentration is real and only partly hedged. Which raises the deepest question in the article, the one no better algorithm can answer: could we ever prove two assumptions uncorrelated, even in principle?
8. Why You Cannot Prove the Portfolio Uncorrelated
Now the bad news that no better algorithm can fix. There are two impossibilities here, and they ascend: the first is well known and merely humbling; the second is specific to this article's thesis and is, in a strict sense, permanent.
The first: nothing in the stack is proven hard. Module-LWE, syndrome decoding, and hash security all rest on the same foundation -- "nobody has broken it yet." The best-known positive result is Regev's: a quantum reduction from worst-case lattice problems to average-case LWE [12]. That is genuine, beautiful evidence: if you could solve random LWE instances efficiently, you could solve the worst case of certain lattice problems too. But it is not a hardness proof, because those worst-case problems are themselves only believed hard.
A problem is worst-case hard if some inputs are hard; it is average-case hard if a randomly chosen input is hard. Cryptography needs the second, stronger property, because keys are random. General decoding is NP-complete in the worst case, but that says nothing about the average random instance a code-based scheme actually uses -- which is why "NP-complete" is a weaker comfort here than it first sounds.
It goes deeper than "we have not gotten around to it." The lattice problems live in a place that makes a proof structurally unavailable.
The class of problems whose yes-answers and no-answers both have short, checkable certificates. The worst-case lattice problems (approximate GapSVP and GapSIVP) that LWE reduces from sit here [39]. That location is itself a clue: problems in NP intersect coNP are believed not to be NP-complete, so lattice hardness cannot simply be inherited from NP-completeness -- and a real hardness proof would have to settle questions about P, NP, and coNP that have resisted half a century of effort.
Why proving any of this hard would be front-page news
Suppose you proved that Module-LWE requires exponential time. You would then have exhibited a problem in NP that is not in P -- which proves P is not equal to NP, the most famous open question in computer science, with a million-dollar prize attached. Every cryptographic hardness assumption is, in this exact sense, a bet on how a Millennium Problem resolves. We build the internet on conjectures because proofs are unavailable, not because anyone is being careless.
The second impossibility is the one this whole article has been circling, and it is worse than the first. Even if, by some miracle, we could prove each assumption individually hard, we still could not prove them uncorrelated. Uncorrelatedness is a statement about all possible future mathematics: that no single idea, in any field, ever reaches two of these problems at once. You can accumulate evidence for it -- watch two assumptions resist different tools, wielded by different communities, for different lengths of time. You can never close it.
SIDH is the proof of the danger: the tool that took it was a 1997 theorem nobody had connected to cryptography. There is no theorem that says "and there are no more surprises like that one."
You cannot prove the portfolio uncorrelated. You can observe that two assumptions have resisted different tools for different lengths of time, but you can never rule out a single future idea that reaches both -- that is not a gap in today's knowledge, it is unprovable in principle. Diversity is therefore risk management, not proof. The portfolio is not a solution to the hardness problem; it is the best available discipline in the permanent absence of one.
This is the moment the comfortable reading breaks. Diversity felt like a solution -- hold different assumptions and relax. It is not a solution. It is a disciplined bet made under permanent uncertainty, chosen precisely because certainty is not on the menu and never will be.
Diversity is the closest thing to a security proof this science permits -- and it is not a proof at all.
If we can neither prove the bets hard nor prove them independent, the only rational questions left are practical ones: where would a correlated break actually come from, and how much time is on the clock?
9. Where the Correlated Break Would Come From
If you wanted to take down the whole stack, here is where you would aim. Three of these questions are open mathematics; the fourth is a clock.
A "Shor for lattices." An efficient quantum algorithm for Module-LWE would be the nightmare scenario: a single result reaching ML-KEM, ML-DSA, and by extension the lattice core all at once -- the correlated break the map warns about. And this is not a thought experiment. In April 2024, Yilei Chen posted a paper claiming exactly such an algorithm. In little more than a week Chen withdrew the claim: a flaw in Step 9, found independently by Hongxun Wu and Thomas Vidick, could not be repaired [40, 41]. It must be cited only as retracted, never as a live break [42].
The algorithm did not survive contact with other experts -- but for a little over a week, serious people believed the lattice core might be gone. That interval is the point. The feared correlated break is unrealized, not impossible, and the field felt exactly how much rides on one assumption.
Whether the signature on-ramp adds real diversity. NIST is still recruiting more signature families, and the roster is a live test of the whole thesis.
The clock. Everything above would be an academic seminar if the timeline were comfortable. It is not, because of a single idea.
The attack that makes migration urgent today even though no quantum computer exists yet. An adversary records encrypted traffic now and stores it, waiting for a future quantum computer to decrypt it retroactively. Any secret that must stay confidential for longer than the time-to-quantum is already exposed, no matter how strong today's key exchange looks.
Michele Mosca turned this into a one-line risk test, : if the years your data must stay secret () plus the years you need to migrate () meet or exceed the years until a cryptographically relevant quantum computer (), your data is already at risk today [45].
# Mosca's inequality: if secrecy_life + migration_time >= time_to_quantum,
# your data is already exposed to harvest-now-decrypt-later.
def already_exposed(secrecy_life_years, migration_years, years_to_quantum):
exposure = secrecy_life_years + migration_years
print("Secrecy lifetime (X): " + str(secrecy_life_years) + " yr")
print("Migration time (Y): " + str(migration_years) + " yr")
print("Time to quantum (Z): " + str(years_to_quantum) + " yr")
if exposure >= years_to_quantum:
print("EXPOSED: X + Y exceeds Z by " + str(exposure - years_to_quantum) + " yr. Migrate now.")
else:
print("Safe for now by " + str(years_to_quantum - exposure) + " yr. Keep watching Z.")
# A record that must stay secret 15 years, a 5-year migration, quantum in 12 years:
already_exposed(15, 5, 12) Press Run to execute.
For many long-lived secrets the inequality already bites, which is why the migration is being written into law rather than left to preference. The alarm is not new -- the NSA signaled it as early as 2015, when it announced plans to move away from its existing Suite B algorithms [46]. It has since hardened into deadlines: CNSA 2.0 sets a 2025-to-2033 timeline for national security systems [38], and Executive Order 14412 codifies migration requirements and the harvest-now-decrypt-later threat directly into federal policy [47].
None of the open questions is settled, and the clock is already running. So the only responsible move is to build a stack today that survives being wrong about any one of them. That turns out to be a concrete engineering task.
10. Building an Uncorrelated Stack on Monday
Strip away the theory. Here is what to deploy, and the single rule that ties it together: watch the assumption, not the algorithm name.
Deploy hybrids. Run a classical key exchange and a post-quantum KEM together and combine their secrets, so that a break of the post-quantum half is not, by itself, a break of the session. The dominant TLS deployment is the hybrid group X25519MLKEM768; the closely related general-purpose combiner X-Wing [34] is built on the same X25519 and ML-KEM-768 primitives.
Diagram source
flowchart LR
X["X25519 shared secret"] --> KDF["Combiner / KDF"]
K["ML-KEM-768 shared secret"] --> KDF
KDF --> S["Session key (secure if either input holds)"] This is not a hypothetical benefit. The empirical case for hybrids is already written. Cloudflare's earlier CECPQ2b experiment paired X25519 with the isogeny KEM SIKE, and any traffic recorded then stayed safe when SIKE broke -- the classical half still held [35]. A hybrid turned a total break into a non-event. A hybrid is the correlation lens applied to a single connection.
// A hybrid combines a classical secret and a post-quantum secret.
// The session key is safe as long as EITHER half is still unbroken.
function hybridSafe(classicalBroken, pqBroken) {
return !(classicalBroken && pqBroken);
}
for (const classicalBroken of [false, true]) {
for (const pqBroken of [false, true]) {
const verdict = hybridSafe(classicalBroken, pqBroken) ? 'SAFE' : 'EXPOSED';
console.log('classical broken=' + classicalBroken +
', PQ broken=' + pqBroken + ' -> ' + verdict);
}
}
// Only the final row, where both are broken, prints EXPOSED. Press Run to execute.
Refuse a lattice monoculture. This is the mistake the whole article exists to prevent.
Pair the efficient lattice core with a backstop that shares nothing with it: SLH-DSA for signatures you need to trust for decades, and a code-based KEM -- HQC or Classic McEliece -- kept available for encryption. And because the lattice margin is the contested one, prefer the higher-margin parameter sets (ML-KEM-768 or 1024) over the smallest.
Build for replacement. No choice here is permanent, so the system must be able to change its mind.
The engineering property of being able to swap a cryptographic primitive without re-architecting the system around it. If your protocol treats "the KEM" as a replaceable module rather than a hardwired choice, then an assumption that starts to erode can be dropped for another before it fails -- which is the operational form of holding a portfolio.
Put together, the decision guide is short, and every row is chosen by assumption, not by benchmark:
| Need | Deploy | Why |
|---|---|---|
| General key exchange | ML-KEM-768, hybridized with X25519 | Efficient lattice core plus a classical backstop |
| Maximum-conservatism encryption | Classic McEliece or HQC | Code assumption, uncorrelated with lattices |
| General signatures | ML-DSA-65, hybridized | Efficient lattice signature with a classical hedge |
| Firmware and root-of-trust signing | SLH-DSA | Hash-only, shares nothing with the rest, longest-lived trust |
| Bandwidth-critical signing | Falcon | Smallest signatures, at the cost of a third lattice bet |
One boundary, named once and handed off: the ways these schemes break in practice -- timing leaks in KEM decapsulation, the delicate floating-point sampling inside Falcon's signer, fault and power attacks -- are implementation attacks, a different and equally real surface owned by the sibling track. This section is about the mathematics you choose to deploy, not the code that runs it.
Every one of these moves is a refusal to concentrate -- the same refusal, at the level of a single deployment, that the whole standardization effort was reaching for. Which brings us back to the thesis, now with all the evidence in.
11. Common Misconceptions, Corrected
The fastest way to misread everything above is to reach for one of these seven conclusions. Each is a precise trap, and each answer defends the portfolio rather than any single scheme.
Frequently asked questions
Is the post-quantum stack broken?
No. Every standardized scheme -- ML-KEM, ML-DSA, SLH-DSA -- currently stands, and HQC has been selected on top of them [19]. The argument of this article is not that the stack is weak. It is that the stack's safety is a diversified portfolio, not the proven hardness of any one algorithm, because none of them is proven hard.
Did not a quantum computer break SIKE?
Was SIKE a NIST standard?
No. SIKE was a Round-4 alternate candidate still under evaluation, and it was broken before any selection was made [4, 3]. It was never standardized. The correct lesson is that a late-stage, heavily vetted candidate can fall without warning -- which is worse, not better, than a fringe scheme failing.
ML-KEM and ML-DSA both use Module-LWE -- does not one break take down both?
A generic, structural break of Module-LWE would indeed threaten both -- that is the correlated-pair risk at the center of the map. But they use different parameters (moduli 3329 versus 8380417, different ranks and noise), and ML-DSA additionally rests on Module-SIS, so a parameter-specific attack on one need not transfer to the other [16, 17]. The correlation is at the level of the shared assumption family, not identical instances.
Is hash-based SLH-DSA doomed when SHA breaks?
Its security is hash security -- that is the design, not a weakness [18]. And SHA-2 and SHA-3 carry the largest, most-scrutinized security margins in all of cryptography. Reducing entirely to that well-studied foundation, while sharing no algebraic structure with lattices or codes, is exactly why SLH-DSA is the conservative anchor of the portfolio.
If nothing is proven hard, why trust any of it?
Because the trust is not placed in one assumption; it is placed in diversity. Lattice, code, and hash rest on unrelated mathematics developed by different communities, and are unlikely to all fall for the same reason at the same time. A break of one leaves the others standing. That is risk management under permanent uncertainty, which is the most any cryptographic science can offer.
Is the March 2025 code-based winner Classic McEliece?
Notice what every answer has in common: not one of them defends a single algorithm. They defend the portfolio.
12. The Portfolio Is the Product
Put the evidence back together. Shor proved that two bets which looked independent -- factoring and discrete log -- were one bet on the abelian hidden-subgroup problem, and fell together the moment the right machine existed [7]. SIDH proved that a family can vanish in an afternoon, classically, with no warning, when a 1997 theorem finally met the auxiliary data the protocol had been publishing all along [1]. And the standardized stack, colored by assumption, clusters onto three families -- lattice, hash, and code -- with a genuinely correlated Module-LWE pair, ML-KEM and ML-DSA, sitting at its efficient center [16, 17].
None of those assumptions is proven hard. None ever will be, short of settling questions about P, NP, and coNP P is the class of problems solvable quickly; NP the class whose solutions can be verified quickly. Whether the two are equal is the central unsolved question of computer science. that have resisted fifty years of effort. And even if they were proven hard one at a time, no theorem could certify them uncorrelated, because uncorrelatedness is a promise about mathematics not yet invented. That is the humbling floor under the entire post-quantum project.
So the security of the stack was never going to be the strength of its strongest algorithm. It is the deliberate, dated refusal to let its bets be correlated: hash-only SLH-DSA standing apart from everything, the March 2025 selection of code-based HQC precisely because it is not a lattice, and an on-ramp still searching for more uncorrelated bets [18, 19]. Diversity here is not a hedge bolted onto the design. It is the design.
That reframes what we have actually been buying all along. Not a proof. A portfolio.
We cannot prove the stack secure. But we can, and did, refuse to bet it all on one piece of mathematics.
This is the sentence you were handed in the first section, now earned. We are not betting on a proof. We are betting that lattice, code, and hash will not all fail for the same reason on the same day -- and we have arranged things so that if we are wrong about one, we are not wrong about all three. For a science that can prove nothing hard, that disciplined refusal to concentrate is not a consolation prize. It is the whole defense, and it is the best one available for the thirty years we are wagering on it.
Study guide
Key terms
- Correlated failure
- Two or more primitives that fail together because they share hidden mathematics
- Abelian hidden-subgroup problem
- The structure Shor exploits; factoring and discrete log are both instances
- Module-LWE
- Noisy linear algebra over module lattices; the shared assumption of ML-KEM and ML-DSA
- Syndrome decoding
- The code-based hard problem behind HQC and Classic McEliece
- Hybrid key exchange
- Combine a classical and a post-quantum secret; secure if either half holds
- Crypto-agility
- The ability to swap a primitive without re-architecting the system
- NP intersect coNP
- Where lattice problems sit, which implies they are believed not NP-complete
Flashcards
Flashcards
1 / 5Comprehension questions
Why is a single-family swap still a monoculture?
It concentrates all security on one hard-problem family, so one advance takes everything -- the mistake Shor punished.
Why can uncorrelatedness never be proven?
It is a claim about all future mathematics; you cannot rule out one idea reaching two assumptions at once. SIDH is the cautionary case.
What does the March 2025 HQC selection demonstrate?
Diversification as explicit, dated policy: a second KEM chosen because it is code-based, not lattice-based.
References
- (2022). An Efficient Key Recovery Attack on SIDH. https://eprint.iacr.org/2022/975 - Classical key recovery of SIKEp434 in about ten minutes on one core. ↩
- (2011). Towards Quantum-Resistant Cryptosystems from Supersingular Elliptic Curve Isogenies. https://link.springer.com/chapter/10.1007/978-3-642-25405-5_2 - SIDH; the protocol publishes torsion-point images by design. ↩
- (2022). PQC Standardization Process: Announcing Four Candidates to be Standardized, Plus Fourth-Round Candidates. https://www.nist.gov/news-events/news/2022/07/pqc-standardization-process-announcing-four-candidates-be-standardized-plus - SIKE advanced to Round 4 on 5 July 2022, about 3.5 weeks before it was broken. ↩
- (2022). NIST IR 8413: Status Report on the Third Round of the NIST PQC Standardization Process. https://csrc.nist.gov/pubs/ir/8413/upd1/final - SIKE advanced to Round 4 as a candidate; never standardized. ↩
- (2005). A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem. https://arxiv.org/abs/quant-ph/0302112 - The dihedral hidden-subgroup quantum bound that applies to CSIDH, not to lattices. ↩
- (1993). The Number Field Sieve and Pollards Rho (classical factoring and discrete-log complexity). - Classical attack complexities that set RSA and ECC parameter sizes. ↩
- (1994). Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. https://doi.org/10.1109/SFCS.1994.365700 - Factoring and discrete log both solved via the abelian hidden-subgroup problem -- the original correlated failure. ↩
- (1996). A Fast Quantum Mechanical Algorithm for Database Search. https://doi.org/10.1145/237814.237866 - Generic quadratic search speedup; absorbed by parameter sizes, not a structural break. ↩
- (1978). A Public-Key Cryptosystem Based on Algebraic Coding Theory. https://classic.mceliece.org/ - Code-based PKC; about 47 years unbroken as a structure. ↩
- (1989). A Certified Digital Signature. https://doi.org/10.1007/0-387-34805-0_21 - Hash-based signatures via trees and one-time signatures; thesis Stanford 1979. ↩
- (1998). NTRU: A Ring-Based Public Key Cryptosystem. https://doi.org/10.1007/BFb0054868 - The short-vector lattice assumption behind Falcon. ↩
- (2005). On Lattices, Learning with Errors, Random Linear Codes, and Cryptography. https://cims.nyu.edu/~regev/papers/qcrypto.pdf - LWE and its quantum worst-case-to-average-case reduction. ↩
- (2025). NTRU Prime. https://ntruprime.cr.yp.to/ - The anti-monoculture rationale: choosing a single system risks a cryptographic monoculture. ↩
- (2019). NIST IR 8240: Status Report on the First Round of the NIST PQC Standardization Process. https://csrc.nist.gov/pubs/ir/8240/final - 82 submissions, 69 accepted, five families. ↩
- (2016). Post-Quantum Cryptography Project. https://csrc.nist.gov/projects/post-quantum-cryptography - The process that built the portfolio; its refusal to standardize one family is the thesis as policy. ↩
- (2024). FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard. https://csrc.nist.gov/pubs/fips/203/final - ML-KEM; security related to Module-LWE, q = 3329. ↩
- (2024). FIPS 204: Module-Lattice-Based Digital Signature Standard. https://csrc.nist.gov/pubs/fips/204/final - ML-DSA; Module-LWE plus Module-SIS, q = 8380417. ↩
- (2024). FIPS 205: Stateless Hash-Based Digital Signature Standard. https://csrc.nist.gov/pubs/fips/205/final - SLH-DSA; security reduces entirely to hash properties. ↩
- (2025). NIST IR 8545: Status Report on the Fourth Round of the NIST PQC Standardization Process. https://csrc.nist.gov/pubs/ir/8545/final - HQC selected 11 March 2025 as the second KEM; why HQC over BIKE and why not McEliece. ↩
- (1996). Generating Hard Instances of Lattice Problems. https://doi.org/10.1145/237814.237838 - First worst-case to average-case lattice reduction. ↩
- (2010). On Ideal Lattices and Learning with Errors over Rings. https://eprint.iacr.org/2012/230 - Ring-LWE: the efficiency that made lattice crypto deployable. ↩
- (2015). Worst-Case to Average-Case Reductions for Module Lattices. https://eprint.iacr.org/2012/090 - Module-LWE, the shared spine of ML-KEM and ML-DSA. ↩
- (2017). CRYSTALS-Kyber: A CCA-Secure Module-Lattice-Based KEM. https://eprint.iacr.org/2017/634 - The Module-LWE KEM that became ML-KEM, q = 3329. ↩
- (2017). CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme. https://eprint.iacr.org/2017/633 - Module-LWE plus Module-SIS signature, q = 8380417; becomes ML-DSA. ↩
- (2016). Post-Quantum Key Exchange -- A New Hope. https://www.usenix.org/system/files/conference/usenixsecurity16/sec16_paper_alkim.pdf - Core-SVP model; lattice sieving cost and the shared nearest-neighbor caution. ↩
- (2012). Decoding Random Binary Linear Codes: How 1+1=0 Improves Information Set Decoding. https://doi.org/10.1007/978-3-642-29011-4_31 - Best classical ISD exponent; the ruler for code-based security. ↩
- (2026). Classic McEliece: ISO Standardization. https://classic.mceliece.org/iso.html - ISO standardized Classic McEliece in June 2026; lists the standardized mceliece parameter sets. ↩
- (2025). Classic McEliece: Security and Comparison. https://classic.mceliece.org/comparison.html - Partisan (McEliece/diversity camp); code-margin stability and NIST Kyber-512 gate figures. ↩
- (1997). The Number of Curves of Genus Two with Elliptic Differentials. https://doi.org/10.1515/crll.1997.485.93 - The reducibility criterion, dormant 25 years, that broke SIDH. ↩
- (2022). Breaking SIDH in Polynomial Time. https://eprint.iacr.org/2022/1038 - The SIDH break runs in classical polynomial time from any starting curve. ↩
- (2022). An Attack on SIDH with Arbitrary Starting Curve. https://eprint.iacr.org/2022/1026 - Generalizes the break and bounds it away from CSIDH and SQIsign. ↩
- (2015). SPHINCS: Practical Stateless Hash-Based Signatures. https://link.springer.com/chapter/10.1007/978-3-662-46800-5_15 - Direct ancestor of SLH-DSA (FIPS 205). ↩
- (2025). HQC: Hamming Quasi-Cyclic. https://pqc-hqc.org/ - Quasi-cyclic code-based KEM; key and ciphertext sizes. ↩
- (2024). X-Wing: The Hybrid KEM. https://eprint.iacr.org/2024/039 - X25519 + ML-KEM-768 general-purpose hybrid KEM; shares its two primitives with the deployed TLS group X25519MLKEM768, which uses a different combiner. ↩
- (2024). The State of the Post-Quantum Internet. https://blog.cloudflare.com/pq-2024/ - About 2 percent of TLS 1.3 to Cloudflare post-quantum by early 2024, over 99 percent from Chrome. ↩
- (2024). iMessage with PQ3: The New State of the Art in Quantum-Secure Messaging. https://security.apple.com/blog/imessage-pq3/ - Production hybrid: P-256 plus ML-KEM for initial establishment and rekeying. ↩
- (2023). Signal PQXDH: Quantum-Resistant Extended Triple Diffie-Hellman. https://signal.org/blog/pqxdh/ - Production hybrid: post-quantum protection at initial key establishment. ↩
- (2005). Lattice Problems in NP intersect coNP. https://doi.org/10.1145/1089023.1089025 - Lattice problems sit in NP intersect coNP, so believed not NP-complete. ↩
- (2024). Quantum Algorithms for Lattice Problems. https://eprint.iacr.org/2024/555 - RETRACTED: the claimed quantum LWE algorithm had an unfixable Step-9 bug. ↩
- (2024). A Quick Post on Chens Algorithm. https://blog.cryptographyengineering.com/2024/04/16/a-quick-post-on-chens-algorithm/ - Named-expert corroboration of the Chen retraction (Wu and Vidick). ↩
- (2024). Scientists Spot Mistake in Proposed PQC-Cracking Algorithm. https://thequantuminsider.com/2024/04/20/update-scientists-spot-mistake-in-proposed-pqc-cracking-algorithm/ - Secondary corroboration of the Chen retraction. ↩
- (2022). Post-Quantum Cryptography: Digital Signature Schemes -- Call for Proposals. https://csrc.nist.gov/projects/pqc-dig-sig/standardization/call-for-proposals - The additional-signatures on-ramp; live hunt for uncorrelated signature bets. ↩
- (2022). Breaking Rainbow Takes a Weekend on a Laptop. https://eprint.iacr.org/2022/214 - Multivariate flagship Rainbow key-recovered in a weekend. ↩
- (2015). Cybersecurity in an Era with Quantum Computers: Will We Be Ready?. https://eprint.iacr.org/2015/1075 - Moscas inequality: secrecy life plus migration time versus time-to-quantum. ↩
- (2015). Planning for the Near-Term Transition to Quantum-Resistant Algorithms. - The institutional starting gun for the migration. ↩
- (2026). Executive Order 14412: Securing the Nation Against Advanced Cryptographic Attacks. https://www.federalregister.gov/documents/full_text/text/2026/06/25/2026-12909.txt - 91 FR 38483; migration deadlines and harvest-now-decrypt-later codified as law. ↩
- (2022). Commercial National Security Algorithm Suite 2.0. https://media.defense.gov/2022/Sep/07/2003076286/-1/-1/0/CSI-CNSA-2-0-FACT-SHEET-U.PDF - Mandates ML-KEM and ML-DSA, plus stateful LMS/XMSS for firmware signing, on a timeline running to 2033. ↩