# Two Standards, One Lattice: How ML-KEM and ML-DSA Would Break
> ML-KEM and ML-DSA rest on one hard problem, Module-LWE, measured by one ruler. Here is how that ruler would slip -- and why one slip debits both standards.
*Published: 2026-07-18*
*Canonical: https://paragmali.com/blog/two-standards-one-lattice-how-ml-kem-and-ml-dsa-would-break*
*© Parag Mali. All rights reserved.*
---
**ML-KEM and ML-DSA are not two security stories -- they are one.** Both rest on a single hard problem, Module-LWE, whose strength is not proven but *measured*, by one number: the BKZ block size that lattice reduction must reach. The realistic "break" is not a sudden collapse but that ruler slipping a few bits at a time as reduction improves -- and because both standards read the same ruler, one advance debits both at once (correlated failure). The wildcards are a still-hypothetical "Shor for lattices" (the closest attempt was retracted within days) and a structural attack on the cyclotomic ring, the one risk the ruler cannot price.
## 1. We Escaped Shor by Making One Bet
We escaped Shor by making a single bet. RSA and elliptic curves fell to a quantum algorithm that hunts for hidden periodic structure, and lattice problems replaced them precisely because they seem to offer no such structure to hunt. In August 2024 the US National Institute of Standards and Technology (NIST) finished the job, publishing ML-KEM as FIPS 203 for key establishment [@fips-203] and ML-DSA as FIPS 204 for signatures [@fips-204]. The celebrations were real. But they skipped an uncomfortable question: if a quantum computer cannot break the replacements the way it broke the originals, how *would* they break?
The honest answer is: not with a bang. ML-KEM and ML-DSA are two products of one assumption, the Module Learning-With-Errors problem, and the strength of that assumption is not proven. It is *measured* -- read off a single ruler that lattice cryptographers argue about openly. The likely failure is not a dramatic event but that ruler slipping, a few bits at a time, as attacks improve. And because both standards are pinned to the same ruler, one slip debits both at once.
> **Key idea:** Two standards, one lattice, one ruler. ML-KEM and ML-DSA do not have two security stories; they have one -- Module-LWE -- read off a single ruler, the core-SVP block size that lattice reduction must reach. The realistic break is that ruler slipping a few bits at a time, and because both standards read the same ruler, one slip debits both at once. A *sudden* break would have to come from the one thing the ruler does not price: the algebra of the cyclotomic ring.
That lens sorts the whole threat surface into three routes, in descending order of likelihood. First and most probable is **erosion**: lattice reduction gets a little better, the ruler reads a few bits lower, and the published margins thin. This has already happened once in miniature, and it is the route this article says you should expect.
The second is **the quantum route** everyone fears -- a "Shor for lattices" that would collapse the margin all at once. It has been claimed exactly once, and retracted within days. The third is the **wildcard**: a structural attack on the extra algebra of the cyclotomic ring, the one surface the ruler does not even try to price. Low probability, high impact, genuinely contested.
> **Note:** This is a structural-cryptanalysis piece. It asks by what *mathematical* route ML-KEM and ML-DSA would fail: attacks on the algorithms' own hardness assumptions. It deliberately excludes implementation attacks -- timing leaks such as KyberSlash, fault and power analysis, random-number-generator failures, and protocol misuse. Those are real and they matter, but they break a particular *program*, not the *mathematics*. They belong to the empirical sibling, "How ML-KEM Breaks in Real Life." One boundary case is worth stating up front: quantum algorithms that attack the math (Shor) are in scope, and we will spend a section explaining precisely why Shor gets no purchase here.
To see how the ruler slips, we first have to see where the hardness came from -- and why "noisy linear algebra" survived the very tools that killed RSA.
## 2. Where the Hardness Comes From
In 1996, at IBM's Almaden Research Center, Miklos Ajtai proved something that sounds too good to be true: certain *random* lattice problems are as hard as the *worst* case of a related problem [@ajtai-1996]. For a cryptographer, that is the dream.
Normally, a randomly generated key gives no guarantee you did not pick an easy instance. Ajtai's worst-case-to-average-case reduction says these lattice problems are different: a random instance is not a roll of the dice -- it inherits the difficulty of the hardest instance that exists. Build your keys on that, and breaking your *average* key would mean breaking the *worst-case* problem everyone believes is hard.
The set of all integer combinations of a fixed set of basis vectors -- a regular, infinite grid of points in $n$-dimensional space. The same lattice has infinitely many bases. The hard problems live in the gap between a "good" basis (short, nearly perpendicular vectors) and a "bad" one (long, skewed vectors) that generate the identical grid.
The grid has a catch that makes it useful. Given a "bad" basis, simple questions become brutal.
Given a basis for a lattice, find the shortest non-zero vector in it. In high dimension, with a bad basis, no efficient algorithm is known -- and the best ones we have get exponentially slower as the dimension grows. Cryptographic hardness is quoted relative to how hard SVP is in the relevant dimension.
Ajtai's foundation was beautiful. The cryptosystems built directly on it were not. The first generation broke almost as fast as it was proposed. The Ajtai-Dwork scheme was provably hard but shipped megabyte-sized keys, and Nguyen and Stern broke it at its proposed parameters in 1998 [@nguyen-stern-1998]. The Goldreich-Goldwasser-Halevi scheme followed the tempting "publish a bad basis, decrypt with a secret good basis" template. Phong Nguyen broke it in 1999 by noticing that its special error distribution leaked a congruence, recovering plaintext outright at four of the five proposed dimensions and most of it at the fifth [@nguyen-ggh-1999].
The lesson was expensive and permanent: hiding a good basis is not enough, because the structure you use to decrypt is structure an attacker can find. The hardness was real; the packaging was hopeless.
The fix arrived in 2005, and it changed the shape of the field. Oded Regev introduced Learning With Errors.
Recover a secret vector $\mathbf{s}$ from many noisy linear samples $(\mathbf{a}_i,\; \langle \mathbf{a}_i, \mathbf{s}\rangle + e_i \bmod q)$, where each $\mathbf{a}_i$ is public and random and each $e_i$ is a small secret error. Without the errors this is a linear system you solve by Gaussian elimination. With them, it is believed hard. LWE is "linear algebra where every equation is slightly, deliberately wrong."
Regev's construction did two things at once. It made the noise *intrinsic* -- the hardness no longer depended on hiding a clever basis, but came from the errors themselves -- and it came with a quantum worst-case-to-average-case reduction connecting a random LWE key to the worst case of standard lattice problems [@regev-lwe-2005]. That word "quantum" is deliberate: Regev's reduction was tuned for a post-quantum world from the start.
It also points at the deeper reason lattices replaced RSA and elliptic curves. [Shor's algorithm](/blog/how-q-day-breaks-everything-shors-algorithm-and-the-simultan/) breaks RSA and Diffie-Hellman because those problems hide a *periodic* structure that a quantum Fourier transform can extract. LWE exposes no such period.This is the one-line reason lattices were chosen for the post-quantum standards: a period-finding or hidden-subgroup quantum algorithm has nothing to grab onto in the geometry of short vectors. Section 7 makes this precise. The very feature that makes LWE resist Shor is that its hardness is geometric, not arithmetic.
You can feel why the noise is load-bearing with a tiny numerical example.
{`
// A toy LWE instance mod q. Recover the secret s from samples (a, b).
const q = 97;
const s = [42, 15, 8]; // the secret we must recover
const dot = (a, b) => a.reduce((t, x, i) => t + x * b[i], 0);
const A = [[12, 5, 33],[7, 88, 1],[54, 2, 19]]; // 3 public random rows
// Case 1: no noise. b = A s mod q. Gaussian elimination recovers s exactly.
const clean = A.map(a => ((dot(a, s) % q) + q) % q);
console.log("clean samples b =", clean);
// With 3 equations and 3 unknowns and NO error, solving is instant and exact.
// Case 2: add a small error e in {-1,0,1} to each equation.
const e = [1, -1, 1];
const noisy = A.map((a, i) => ((((dot(a, s) + e[i]) % q) + q) % q));
console.log("noisy samples b =", noisy);
// Now the linear system is INCONSISTENT with the true s: every naive solve
// that assumes e = 0 returns a different, wrong vector. The attacker must
// search over which tiny error vector was added -- and in real dimensions
// (n = 256 and up) that search is the hard lattice problem itself.
console.log("difference caused by e =", noisy.map((b, i) => b - clean[i]));
`}
Three equations in three unknowns is trivial. The standards use dimensions in the hundreds, and the error turns "solve the system" into "find a suspiciously short vector in a lattice built from the system" -- which is SVP wearing a disguise. That disguise is the entire security story. The rest of this article is about how sharp the disguise really is.
LWE did not appear from nowhere; it was the turning point of a forty-year accretion, and seeing that lineage explains why the eventual break is an endpoint, not a surprise.
flowchart LR
A["LLL basis reduction, 1982"] --> B["Ajtai worst-case hardness, 1996"]
B --> C["Regev LWE, 2005"]
C --> D["Ring-LWE, 2010"]
D --> E["Module-LWE, 2015"]
E --> F["Kyber and Dilithium, 2017-2018"]
F --> G["FIPS 203 and FIPS 204, 2024"]
The oldest box on that diagram, the LLL algorithm of 1982, is not a footnote [@lll-1982]. It is the ancestor of every attack in this article: the first efficient method to take a bad basis and grind it into a better one. LWE was hard and clean, but its keys were quadratic in the security parameter -- far too heavy to ship in a TLS handshake. The fix was to add structure. And structure, it turns out, is exactly where the danger lives.
## 3. Building the Spine: From LWE to Module-LWE
The efficiency move came in 2010, and it came with a bill the field is still arguing about. Vadim Lyubashevsky, Chris Peikert, and Oded Regev introduced Ring-LWE, which shrinks LWE's quadratic keys to quasi-linear by pouring all the algebra into a single polynomial ring [@ring-lwe-lpr-2010]. Instead of storing a full random matrix $\mathbf{A}$, you store one polynomial and let the ring's multiplication *generate* the matrix. Multiplication becomes a number-theoretic transform, the same fast-Fourier trick that makes the schemes practical on a phone. Keys drop from megabytes to kilobytes. Without this step there is no shippable post-quantum handshake.
But look at what changed. In plain LWE the matrix $\mathbf{A}$ is fully random -- every entry independent. In Ring-LWE that matrix is *generated by one polynomial*, so its entries are locked together in a rigid, algebraic way. That relatedness is exactly what makes the scheme fast. It is also what has divided lattice cryptography ever since: does the ring structure only buy speed, or does it also buy the attacker a shortcut?
Daniel Bernstein and the NTRU Prime team have argued for years that the extra structure is an under-appreciated risk, and they built their alternative to avoid the most structured ring choices [@bernstein-kyber512-2023]. The design teams and NIST bet the other way. Section 8 weighs that dispute; for now, note only that it is real and unresolved.
The standards did not take either extreme. They took the middle, on purpose.
LWE instantiated over a rank-$k$ module of a polynomial ring: instead of one big structured polynomial (Ring-LWE) or a fully random matrix (plain LWE), you use a small matrix *of* ring elements at module rank $k$ (square $k \times k$ for ML-KEM; rectangular $k \times l$ -- such as $6 \times 5$ or $8 \times 7$ -- for ML-DSA). It is the deliberate middle ground -- most of Ring-LWE's speed, but the single-ring symmetry diluted across $k$ components. This is the shared spine of both FIPS standards.
Damien Stehle and Adeline Langlois gave this middle ground its worst-case-to-average-case reduction in 2015, proving that module lattices inherit the same style of hardness guarantee Ajtai and Regev had established for their settings [@langlois-stehle-2015]. That reduction is what lets the designers treat Module-LWE as a trustworthy foundation rather than an ad-hoc compromise. The rank $k$ becomes a dial: turn it up and you dilute the ring structure toward plain LWE (safer, heavier); turn it down toward $k=1$ and you recover Ring-LWE (faster, more structured). The hedge is built into the assumption itself.
The Short Integer Solution problem over modules: find a short, non-zero combination of given ring vectors that sums to zero. It is a "find a short collision" problem, dual in flavor to Module-LWE's "recover a short secret." ML-DSA depends on Module-SIS for unforgeability; ML-KEM does not carry this assumption at all.
Module-SIS is the second load-bearing assumption, and it matters for the asymmetry at the heart of this article: it is carried by the signature and not by the key-encapsulation mechanism. Both schemes then live in the same specific algebraic home.
The ring $\mathbb{Z}_q[X]/(X^{256}+1)$ that both standards build on: polynomials of degree below 256, with coefficients modulo $q$, reduced whenever the degree reaches 256 by the rule $X^{256} = -1$. Because $256$ is a power of two, this is a "power-of-two cyclotomic" ring -- the most efficient choice, and the one whose extra algebra is the wildcard's attack surface.
flowchart LR
A["Plain LWE: fully random matrix, no ring structure, safest, keys too heavy to ship"] --> B["Module-LWE: small matrix of ring elements, structure diluted across rank k, the tuned middle"]
B --> C["Ring-LWE: one polynomial generates everything, fastest, most structured"]
The through-line from 1998 is worth naming, because the worry is as old as the efficiency trick.NTRU, published in 1998 by Hoffstein, Pipher, and Silverman, was the original "put the lattice in a polynomial ring to make it fast" cryptosystem [@ntru-1998]. It is simultaneously the ancestor of every ring-based scheme here and the origin of the recurring worry that ring structure buys the attacker something. Its descendants include the Falcon signature, whose different spine we meet in Section 4. The field has known since NTRU that ring structure is a bargain with two sides. Module-LWE is the current answer to "how much structure dare we cash in?"
Module-LWE is the single object both FIPS standards are built on: same ring, same core problem, two products. Which raises the question that defines this whole article. If they share one foundation, do they share one failure?
## 4. Two Standards, One Assumption
Lay the two standards side by side and they resolve into one. ML-KEM, the key-encapsulation mechanism in FIPS 203, rests on Module-LWE alone, over the ring $\mathbb{Z}_q[X]/(X^{256}+1)$ with modulus $q = 3329$, and offers three parameter sets at module ranks 2, 3, and 4 [@fips-203]. ML-DSA, the signature in FIPS 204, rests on Module-LWE *and* Module-SIS, over the *same* ring but with a *different*, much larger modulus $q = 8380417$, and signs using Fiat-Shamir with aborts [@fips-204]. Same spine, different parameters.
| Property | ML-KEM (FIPS 203) | ML-DSA (FIPS 204) |
|---|---|---|
| Purpose | Key encapsulation | Digital signatures |
| Core hardness | Module-LWE | Module-LWE + Module-SIS |
| Ring | $\mathbb{Z}_q[X]/(X^{256}+1)$ | $\mathbb{Z}_q[X]/(X^{256}+1)$ |
| Modulus $q$ | 3329 | 8380417 |
| Module ranks | 2 / 3 / 4 (square $k \times k$) | grows with level (rectangular $k \times l$) |
| Signing structure | not applicable | Fiat-Shamir with aborts |
| Extra structural route | decryption failure | SelfTargetMSIS forgery |
| A Module-LWE break yields | the decryption key | the signing key (universal forgery) |
The table's most important row is the third from the bottom, and it hides in plain sight. Both public keys *are*, essentially, the same object: a Module-LWE sample $\mathbf{t} = \mathbf{A}\mathbf{s} + \mathbf{e}$, a structured matrix times a short secret plus a small error. For ML-KEM the public key is literally such a sample, and recovering $\mathbf{s}$ *is* recovering the decryption key.
For ML-DSA the public key is the same shape, and recovering the short secret *is* recovering the signing key -- which lets an attacker forge any signature at will. In both cases the attack is one thing: solve search-Module-LWE, find the short secret hiding in the sample. This is the mechanism the whole article turns on.
> **Key idea:** Correlated failure. Because each public key is a Module-LWE sample read off the same ruler, a single advance in lattice reduction against Module-LWE debits *both* standards at once -- the key-encapsulation mechanism and the signature together. It is not two independent bets. It is one bet, made twice.
The correlation is real, but it is *one-directional*, and precision here matters. A Module-LWE or lattice-reduction advance hits both schemes. But each scheme also carries one extra structural route the other does not share. ML-DSA has a second forgery path through its extra assumption; ML-KEM has a second path through decryption failures. Neither of those extra routes touches the other scheme, and because the two standards use different moduli, ranks, and noise, the *same* reduction advance erodes them by *different* amounts. "Correlated" does not mean "identical."
flowchart TD
A["Module-LWE hardness, the shared spine"] --> B["ML-KEM public key, a Module-LWE sample"]
A --> C["ML-DSA public key, a Module-LWE sample"]
R["A lattice-reduction advance"] --> A
B --> D["Recover the ML-KEM decryption key"]
C --> E["Recover the ML-DSA signing key, universal forgery"]
C --> F["Extra ML-DSA route: SelfTargetMSIS forgery"]
B --> G["Extra ML-KEM route: decryption-failure attack"]
To see why ML-DSA's forgery route is separate, you need its signing template.
ML-DSA's signature method. It builds a signature the Fiat-Shamir way -- commit, hash the message to derive a challenge, respond -- but then *rejection-samples*: any candidate signature whose distribution would leak information about the secret key is thrown away ("abort") and the signer retries. The published signatures are therefore distributed independently of the signing key, so the only structural way to forge is to solve the underlying short-vector problem directly.
Vadim Lyubashevsky introduced the "with aborts" idea in 2009 [@lyubashevsky-fswa-2009] and made it a trapdoor-free lattice signature in 2012 [@lyubashevsky-sigs-2012]; ML-DSA is its standardized descendant [@dilithium-2018] [@pq-crystals-dilithium]. The rejection step is why forging ML-DSA reduces to a specific hard problem, called SelfTargetMSIS, rather than to "study enough signatures until the key leaks." That closed door matters, because it was wide open in an earlier generation.
Correlated failure only bites if the shared foundation can actually be eroded. So how does anyone measure how close an attack is to succeeding? The answer is a single number -- and it is emphatically not a proof.
## 5. The Ruler: How the Margin Is Measured
Here is the uncomfortable truth behind every "128-bit security" claim you have ever read about these schemes: there is no proof of it. There is a *measurement*, taken with a model that the people who built it will happily tell you is simplified and conservative. To understand how ML-KEM and ML-DSA would break, you have to meet the ruler that says how strong they are today.
The best known attacks all reduce to lattice reduction, and the workhorse is BKZ, the block-wise reduction introduced by Schnorr and Euchner in 1994 [@bkz-1994].
Block Korkine-Zolotarev reduction improves a lattice basis by repeatedly calling a subroutine -- an "SVP oracle" -- that solves the shortest-vector problem exactly inside projected blocks of $\beta$ consecutive basis vectors. A larger block size $\beta$ produces shorter vectors and can break harder instances, but the oracle's cost grows sharply with $\beta$. Concrete security is quoted as "the block size $\beta$ that BKZ must reach to solve this instance."
The whole security estimate then collapses onto the cost of one oracle call. The cheapest known way to run that oracle is lattice sieving, and in 2016 Becker, Ducas, Gama, and Laarhoven pinned its cost: a sieve solves SVP in a block of size $\beta$ in time $2^{0.292\beta + o(\beta)}$ using $2^{0.208\beta}$ memory [@bdgl16-sieving]. That exponent, $0.292$, is one of the most consequential constants in modern cryptography. The conservative way to price a whole attack is to charge for just that single most expensive call and ignore everything else.
The deliberately pessimistic (for the defender) cost model that prices an entire lattice attack at the cost of one SVP-oracle call at the required block size: $2^{0.292\beta}$ classical, $2^{0.265\beta}$ quantum. It ignores the many other operations a real attack needs, the cost of memory, and any structure the ring might offer. Because it charges the attacker so little, a scheme that looks secure under core-SVP has margin to spare -- but the number is a modeling choice, not a theorem.
The model originated with the NewHope proposal in 2016 [@newhope-2016]. It was operationalized by the LWE estimator of Albrecht, Player, and Scott, which turns a parameter set into a predicted block size and bit-cost [@aps-estimator-2015]; its maintained successor is the tool NIST parameters are checked against [@lattice-estimator-tool].The estimator is open source. Anyone can install it and re-read the ruler for any parameter set -- which is exactly why the margin is a public, moving number rather than a vendor secret. You can feel the ruler directly: the bit-cost is just the exponent, so a block size and a constant are all you need.
{`
// Core-SVP prices an attack at ONE sieve-oracle call at block size beta.
// The base-2 log of the cost is simply constant * beta, so the exponent
// IS the bit-security number. No astronomically large integers needed.
const bits = (constant, beta) => (constant * beta).toFixed(1);
const beta = 406; // ML-KEM-512's required block size
console.log("ML-KEM-512, beta =", beta);
console.log("classical core-SVP 0.292*beta =", bits(0.292, beta), "bits");
console.log("quantum core-SVP 0.265*beta =", bits(0.265, beta), "bits");
console.log("refined quantum sieve 0.2570 =", bits(0.2570, beta), "bits");
// Now watch the ruler SLIP. Shave the classical constant a hair, from 0.292
// to 0.280 -- the kind of change a better sieve could deliver -- and see how
// many bits of "security" evaporate from the same, unchanged lattice.
console.log("if the constant drops to 0.280:", bits(0.280, beta), "bits");
console.log("bits lost from a 0.012 change =", (bits(0.292,beta) - bits(0.280,beta)).toFixed(1));
`}
Run it and the classical figure lands near $2^{118}$ -- the pure core-SVP number for ML-KEM-512. Now notice what the last two lines show: nudging the exponent constant by twelve thousandths erases almost five bits from an *unchanged* lattice. The ruler is not carved in stone. Its markings move whenever someone finds a better sieve. That is the entire thesis in one code block.
And the disagreement is not hypothetical. The *same* ML-KEM-512 lattice reads wildly differently depending on which model you trust.
| Cost model for ML-KEM-512 | Reads as | What it actually counts |
|---|---|---|
| Pure core-SVP | about $2^{118}$ | one sieve-oracle call, $2^{0.292\beta}$ at $\beta \approx 406$ [@lattice-estimator-tool] |
| Estimator default (ring operations) | about $2^{143.8}$ | ring operations across the whole attack, not just one call |
| NIST gate model | $2^{135}$ to $2^{165}$ | logical gates with the cost of memory access priced in |
One lattice. Three models. Tens of bits apart. NIST's own Kyber-512 analysis concedes the spread openly, estimating that the real gate count "would range from $2^{135}$ to $2^{165}$" depending on how you model memory [@nist-kyber512-faq]. That range is not a rounding error; it is the margin the thesis says is slipping, written down as a live interval by the standardizer itself.
> **Note:** The break is not a bang; it is a ruler slipping. There is no proof behind "128-bit security" for these schemes -- only a measurement, on a conservative and openly debated model whose defining property is that it moves. The likely break is not an event you watch happen. It is an erosion that has already begun, on a spreadsheet.
That reframes the entire question the article opened with. We were looking for the dramatic moment a scheme "cracks." There may never be one. There is a number, and it drifts.
The debate over how to read the ruler is public and pointed. Daniel Bernstein has argued that NIST's Kyber-512 accounting mixes up its arithmetic.
"NIST's primary error ... boils down to nonsensically multiplying two costs that should have been added." -- Daniel J. Bernstein, on the Kyber-512 gate-count dispute
One precaution before we watch the ruler move, because two different quantities share the same number.The sieving exponent $2^{0.292n}$ describes the cost of sieving in the full sieve dimension $n$; the core-SVP figure $2^{0.292\beta}$ describes one oracle call in a block of size $\beta$. They share the constant $0.292$ because both are sieving, but they measure different objects. Conflating them is a classic way to misread the ruler by hundreds of bits. Sieving is not the only oracle, either: the older approach, enumeration, runs in time $2^{\Theta(\beta \log \beta)}$ with only polynomial memory [@bkz2-chen-nguyen-2011]. Sieving wins on time at cryptographic block sizes, which is why the standards are set against it -- but the "best" oracle is itself a moving research target, another reason the ruler is provisional.
Concretely, the trusted way to read the ruler is the primal attack.
flowchart TD
A["Public key: a Module-LWE sample"] --> B["Embed it into a lattice whose shortest vector encodes the secret"]
B --> C["Run BKZ with block size beta"]
C --> D["Each step calls the sieve SVP oracle, cost 2 to the 0.292 beta"]
D --> E["At large enough beta, the short secret vector appears"]
E --> F["Recover the secret: decryption key or signing key"]
The primal attack embeds the public key into a lattice engineered so its shortest vector *is* the secret, then reduces until that vector surfaces [@aps-estimator-2015]. It is the binding constraint -- the number NIST fixes parameters against -- because it relies on no fragile statistical distinguisher, only on reaching the block size. A ruler that is a debated model rather than a proof has one defining property: it moves. And it has moved before.
## 6. The Likely Break: Erosion
The break already had a rehearsal. In 2022 a research unit of the Israeli Defense Forces known as MATZOV published an improved dual lattice attack and reported that it shaved measurable margin off the very schemes NIST was about to standardize [@matzov-2022]. No scheme collapsed. No key was recovered. A number moved on a spreadsheet -- and that is exactly what the likely break looks like.
"Combining these improvements considerably reduces the security levels of Kyber, Saber and Dilithium ... bringing them below the thresholds defined by NIST." -- MATZOV, Report on the Security of LWE, 2022
Read that quote against the thesis. One attack, aimed at the shared Module-LWE spine, moved *both* Kyber (now ML-KEM) [@kyber-2018] and Dilithium (now ML-DSA) at once. That is correlated failure in miniature: not a metaphor, a measurement. And it moved them by *different* amounts, because their parameters differ -- exactly the one-directional, unequal correlation Section 4 predicted.
MATZOV was not a bolt from the blue. It was the latest step in a cryptanalysis lineage that has been quietly moving the ruler for forty years.
| Advance | Year | Effect on the ruler |
|---|---|---|
| LLL basis reduction | 1982 | first efficient reduction; makes weak bases tractable |
| BKZ with enumeration | 1990s-2011 | block reduction; oracle cost $2^{\Theta(\beta \log \beta)}$ |
| Lattice sieving (BDGL16) | 2016 | cheaper oracle, $2^{0.292\beta}$ -- the modern classical constant |
| Improved dual attack (MATZOV) | 2022 | dual sieving plus an FFT distinguisher; thins Kyber-512 below a clean 128 |
Each row lowered the block size an attacker needs, or the cost per block -- which is the same thing as lowering the bit-security the ruler reports. None of them "broke" anything. All of them moved the number.
But honesty about erosion cuts both ways, and the MATZOV figure is itself contested. In 2023, Ducas and Pulles examined the dual-attack family and found its success-probability heuristics internally inconsistent in some regimes -- a "waterfall-floor" behavior in which the predicted advantage is, in their words, presumably significantly overestimated [@ducas-pulles-2023].
So the *precedent* is solid: dual attacks improved and the estimates dropped. The *exact magnitude* of the drop is a live, disputed number. This is why any specific bit-count in this debate must name its model and source -- and why "the margin is a moving estimate" is more accurate than any single figure.
The dual attack does not look for the short secret directly. It works in the *dual* lattice: it guesses part of the secret, then uses short vectors of the dual lattice as a statistical distinguisher -- run through a fast Fourier transform over the guessed coordinates -- to test whether the guess was right. MATZOV's contribution was a faster way to produce those dual vectors (dual sieving) and a sharper distinguisher [@matzov-2022]. The catch Ducas and Pulles identified is that the standard heuristic for the distinguisher's success probability is internally inconsistent: in some regimes it predicts a probability that a more careful analysis contradicts, producing the tell-tale "waterfall-floor" curve, so the claimed advantage is likely overstated [@ducas-pulles-2023]. This is why the *direction* of the erosion is trusted but the *magnitude* is not, and why the primal attack -- which has no such fragile distinguisher -- remains the number parameters are actually fixed against.
There is also a large, reassuring gap between the theory and what anyone can actually do.The primal attack on ML-KEM-512 needs a block size of about $\beta \approx 406$ [@lattice-estimator-tool]. The public record for a solved shortest-vector challenge, tracked on the SVP Challenge Hall of Fame, stands near dimension 210 [@svp-challenge]. The distance between "the block size the ruler says you need" and "the block size anyone has ever reached" is the practical safety margin -- and it is enormous. The reference sieving implementations that hold those records are highly optimized and public [@g6k-2019], which makes the record a meaningful ceiling rather than a guess. Erosion is real, but the frontier of the *achievable* is far below the frontier of the *estimated*.
The key-encapsulation mechanism carries one more erosion axis of its own, and it is purely structural -- a property of the parameters, not of any particular program. ML-KEM's decryption is not guaranteed to succeed: there is a tiny probability that Module-LWE noise plus the rounding in ciphertext compression pushes a coordinate across a decoding boundary, and the recovered key is wrong.
The design fixes this by parameter choice. The round-3 Kyber specification targets decryption-failure probabilities of $\delta = 2^{-139}$, $2^{-164}$, and $2^{-174}$ for the three levels -- all comfortably below $2^{-128}$ -- and the modulus $q = 3329$ was chosen partly to keep that probability negligible [@kyber-round3-spec].
Why does this matter for a *break*? Because decryption failures leak. D'Anvers, Guo, and collaborators showed that observed failures can be turned into full secret-key recovery [@danvers-guo-2019]; "failure boosting" uses precomputation to hunt for failure-inducing ciphertexts [@danvers-vv-2019]; failures cluster, so one found failure makes the next more likely [@bindel-schanck-2020]; and "directional" boosting exploits that clustering, so the cost is dominated by finding the *first* failure [@danvers-rossi-virdia-2020].
It is a genuine structural attack surface -- and at the standardized parameters it is closed, because those same analyses find the required number of oracle queries sits above any practical limit thanks to the conservative $\delta$ [@danvers-vv-2019]. It is the mirror image of ML-DSA's extra forgery route: real, scheme-specific, and neutralized by the parameter margin, not by luck.
> **Note:** Concrete security for ML-KEM and ML-DSA is a measurement that erodes, not a lock that snaps. The realistic failure mode is the estimator reading a few bits lower after the next reduction paper, not a morning when the schemes stop working. This is why crypto-agility matters more than any single parameter choice, and why "watch the estimator, not the headlines" is the operative advice.
That insight organizes the rest of the threat surface. Erosion is the likely route; two tail risks would not be gradual at all.
flowchart TD
A["How Module-LWE would break"] --> B["Erosion: better lattice reduction (LIKELY)"]
A --> C["Quantum: a Shor for lattices (FEARED)"]
A --> D["Ring: cyclotomic structural attack (WILDCARD)"]
B --> B2["Gradual: the ruler slips a few bits at a time"]
C --> C2["Sudden and total, but so far unrealized"]
D --> D2["Sudden and total, low probability, high impact"]
One boundary marker before we go on. None of this section is about KyberSlash. That family of timing and division side channels is an *implementation* leak -- a bug in how a particular program computes, not a weakness in the mathematics -- and it belongs to the empirical sibling, "How ML-KEM Breaks in Real Life." Erosion is the likely structural break. Take the quantum tail risk next, because it is the one everyone fears.
## 7. The Quantum Axis: Feared, Not Realized
The nightmare has a name -- "a Shor for lattices" -- and for about a week in April 2024 it looked like it had arrived. Yilei Chen posted a claimed polynomial-time quantum algorithm for LWE [@chen-2024-retracted]. Had it held, it would have implied a quantum polynomial-time solver for standard lattice problems within an approximation factor of $\tilde{\Omega}(n^{4.5})$ -- close enough to matter, and built on genuinely new machinery: a complex-Gaussian construction its author called a "Karst wave," driven through a windowed quantum Fourier transform. For a few days the post-quantum transition held its breath.
Then it broke -- the claim, not the schemes. Within days, Hongxun Wu and Thomas Vidick identified a fatal error in Step 9, and Chen retracted the result himself.
"Step 9 of the algorithm contains a bug, which I don't know how to fix ... the claim of showing a polynomial time quantum algorithm for solving LWE ... does not hold." -- Yilei Chen, retraction note, 2024
> **Note:** The Chen algorithm is not a live threat and must not be cited as one. It is the single most important recent data point about the *absence* of a quantum lattice break: the best attempt by a strong cryptographer, using new tools, failed at one step. That is evidence of difficulty, not of imminent collapse.
Set the fear against what quantum computers actually buy against lattices, which is modest. Quantum *sieving* speeds up the SVP oracle from $2^{0.292\beta}$ to about $2^{0.265\beta}$, later refined to roughly $2^{0.2570\beta}$ [@chailloux-loyer-2021]. That is a discount on the exponent, not a change in kind -- and it assumes cheap, large-scale quantum RAM that does not exist. It shaves bits; it does not collapse the problem. The refined quantum constant is why the higher parameter sets keep a comfortable margin even against an idealized quantum sieve.
Why does the big speedup keep not arriving? Because the structure Shor exploits is simply not present.
That leaves only Grover's algorithm, and it is not a structural break at all.Wu and Vidick found the Step-9 bug in Chen's algorithm independently and within days, which is itself a sign of how carefully the community watches this line of work. Separately, Grover's algorithm offers a generic square-root speedup on brute-force key search -- effectively halving the security level in the exponent -- which the standards simply absorb by choosing larger parameters. It is named once and set aside, because it applies to every cryptosystem equally and exploits nothing about lattices. Grover turns a $2^{n}$ search into a $2^{n/2}$ one; the parameter sets are sized so that even after that discount the key-search cost stays out of reach. It is a reason the numbers are what they are, not a route to a break.
Quantum is the feared route that keeps not arriving. The other tail risk is quieter, older, and the one the ruler literally cannot price: the algebra of the ring itself.
## 8. The Wildcard: The Cyclotomic Ring
The core-SVP ruler measures one thing: how hard it is to find a short vector by generic lattice reduction. It does not measure whether the *algebra* of the ring offers a shortcut that reduction never sees. That unpriced surface is the wildcard, and intellectual honesty demands steelmanning the people who worry about it, because they have been right before.
Ring structure has been cashed in for real attacks. In 2016, Cramer, Ducas, Peikert, and Regev showed a quantum polynomial-time (classically sub-exponential) algorithm that recovers short generators of principal ideals in cyclotomic fields -- a structural shortcut that plain lattice reduction does not find [@cdpr-2016]. The same year, Albrecht, Bai, and Ducas broke "overstretched" NTRU by projecting the problem into a subfield, exploiting ring structure that appears when the modulus is very large [@albrecht-bai-ducas-2016].
Neither attack touches ML-KEM or ML-DSA at their standardized parameters -- the first needs principal ideals with unusually short generators, the second a modulus far larger than the standards use -- but both prove the general point: structure is not free, and sometimes the attacker gets to spend it. This is why Daniel Bernstein and the NTRU Prime team argue the cyclotomic choice is an under-appreciated risk and deliberately avoid the most structured rings in their own designs [@bernstein-kyber512-2023].
Now the counterweight, weighed just as fairly. First, Module-LWE was chosen partly to dilute exactly this risk: spreading the problem across a rank-$k$ module reduces the single-ring symmetry an algebraic attack would exploit. Second, at the standardized parameters, no known algebraic attack beats generic sieving -- the ideal and subfield attacks live in regimes the standards specifically avoid.
Third, and most concretely, the newest analysis points the *other* way. In 2025, Ducas, Engelberts, and de Perthuis studied module-lattice reduction directly and found that for the power-of-two cyclotomic ring -- exactly the ring ML-KEM and ML-DSA use -- the module structure gives the attacker no free reduction in block size [@ducas-mbkz-2025]. If anything it costs a little: their module-BKZ prediction needs a block size larger by roughly $(d-1)$. The ring the standards chose is, by this measure, a slight *disadvantage* to the attacker, not a gift.
The power-of-two choice is deliberate and load-bearing. Bernstein's NTRU Prime avoids power-of-two cyclotomics on principle, precisely because *other* cyclotomic fields carry more exploitable algebra. And the 2025 module-reduction analysis finds that non-power-of-two cyclotomic fields can yield a sub-exponential module-BKZ gain, whereas the power-of-two ring yields none [@ducas-mbkz-2025]. The standards picked the ring that gives the attacker the least algebraic help, not the most.
Put the three routes on one page and the wildcard sits where it belongs.
| Route | Likelihood | Impact | Best evidence it is real | Counterweight |
|---|---|---|---|---|
| Erosion (better reduction) | Likely | Gradual, partial | MATZOV 2022 moved the published margin | Huge gap: $\beta \approx 406$ needed vs SVP record near 210 [@lattice-estimator-tool] [@svp-challenge] |
| Quantum (a Shor for lattices) | Feared | Sudden, total | Chen 2024 attempt using new machinery | Retracted in days; quantum sieve is only a modest discount |
| Ring (cyclotomic structure) | Wildcard | Sudden, total | Ideal and subfield attacks on adjacent variants | Diluted by modules; no free block-size at power-of-two (2025) |
The honest reading of that table is not "relax." It is "the two catastrophic routes are unrealized and actively fenced off, while the likely route is gradual and observable." That asymmetry is the entire risk posture of lattice cryptography.
NIST reads it the same way, and hedged accordingly. In March 2025 it selected the code-based key-encapsulation mechanism HQC as a backup to ML-KEM [@nist-hqc-announcement], explicitly as insurance against a systemic weakness in lattices [@nist-ir-8545]. That is not a vote of no confidence in ML-KEM; it is a standardizer refusing to make the entire post-quantum transition depend on a single hard problem.
The ring wildcard is low-probability, high-impact -- and honestly labeled as such. But naming it forces a deeper and more uncomfortable question. How much of any of this is actually *proven*?
## 9. What Is Actually Proven
Here is the honest accounting, and it is more humbling than the marketing suggests. Lattice hardness is *unproven* -- and, in a precise sense, it cannot be proven to the standard people quietly assume it meets.
Start with the ceiling. The approximate shortest-vector problem relevant to cryptography -- GapSVP with an approximation factor around $\sqrt{n}$ -- was shown by Aharonov and Regev in 2005 to lie in $\mathrm{NP} \cap \mathrm{coNP}$ [@aharonov-regev-2005]. That single fact has a large consequence: a problem in $\mathrm{NP} \cap \mathrm{coNP}$ is very unlikely to be NP-hard, because if it were, the polynomial hierarchy would collapse. So lattice cryptography can *never* be founded on NP-completeness. The dream of "as hard as the hardest problems in NP" is off the table by a theorem.
The flip side is just as sobering: a genuine *proof* that these problems are hard would prove $\mathrm{P} \neq \mathrm{NP}$ and settle the biggest open question in computer science. Nobody expects that proof. Security rests on the *failure of decades of effort* to find an efficient algorithm, not on a lower bound.
Then there are the reductions everyone points to -- Ajtai's, Regev's, Langlois and Stehle's. They are real and they are beautiful, but read their quantifiers carefully.
An *asymptotic* hardness result says a problem is hard "for all large enough $n$," with unspecified constants. A *concrete* security claim says a specific instance -- $n = 256$, $q = 3329$ -- costs a specific number of operations to break. The worst-case-to-average-case reductions for lattices are asymptotic. They guarantee that *some* sufficiently large parameter is hard; they do not pin the bit-security of the exact parameters a standard ships.
This is the gap the ruler papers over, and it has two halves. First, the reductions are asymptotic: they never certify $n = 256$ specifically, so the concrete strength of the standardized parameters is an estimate, not a corollary.
Second, even the *estimate* trusts a heuristic. The provable cost of solving SVP is around $2^{n}$, but concrete security is quoted using the heuristic sieving cost $2^{0.292n}$ that the estimator actually runs [@bdgl16-sieving]. The number protecting your data is the smaller, unproven one. Both halves point the same way: concrete lattice security is a carefully argued *belief*, propped up by a conservative model, not a theorem.
> **Key idea:** This is the same epistemic position RSA has always occupied -- on a younger assumption. RSA's security was never proven either; it rests on the enduring failure to factor efficiently. Lattice security rests on the enduring failure to reduce lattices efficiently. The difference is only age and exposure: factoring has been hammered for decades longer than Module-LWE has existed. "Believed hard, and watched closely" is the honest label for both.
That reframing turns the open problems from anxieties into a research agenda, and they are worth stating as the questions they are. Is there a large quantum speedup for lattices -- a working version of what Chen 2024 reached for? Is the cyclotomic ring structure exploitable at cryptographic sizes, or does the power-of-two choice hold? And how tight is the core-SVP model really -- what is the true cost of one sieve call, once memory and data movement are honestly priced? Each of these is being worked on in the open, and the answer to each moves the ruler.
None of this means ML-KEM and ML-DSA are weak. It means their strength is a measured, moving, human judgment rather than a settled fact -- which is exactly why what you do with them on Monday matters.
## 10. What to Do on Monday
If the ruler moves, engineering to a single fixed number is the wrong instinct. Engineer for headroom, and engineer for change. Five moves follow directly from everything above.
Prefer the higher parameter set for anything long-lived. ML-KEM offers levels 512, 768, and 1024; ML-DSA offers a matching ladder up to ML-DSA-87 [@fips-203] [@fips-204]. The smallest set, Kyber-512, is where the margin debate is sharpest, so for data that must stay secret for a decade, choose ML-KEM-1024 and the high ML-DSA level and buy yourself bits the estimator cannot easily erase. Even the design team's conservative reading places the middle set, Kyber-768, near AES-192 and treats it as the sensible default [@pq-crystals-kyber].
Deploy in [hybrid](/blog/q-day-has-not-happened-the-incident-already-has-harvest-now-/). Run the post-quantum key exchange alongside a classical one (X25519 or a P-curve) and combine both secrets, so a break of the lattice problem is not a single point of failure -- the classical layer still stands, and vice versa. This is the mainstream transition posture for exactly the reason this article gives: correlated failure across the lattice standards means a lattice break is systemic, and a non-lattice layer is the cheapest insurance against it.
Build crypto-agility. The lesson of the moving ruler is that today's parameters are a snapshot. Architect so that swapping a parameter set -- or an entire algorithm -- is a configuration change, not a rewrite. The sibling articles on [crypto-agility](/blog/you-cannot-rotate-what-you-cannot-see-crypto-agility-and-the/) and [the post-quantum toolkit](/blog/one-event-three-assumptions-five-answers-a-field-guide-to-th/) go deeper here; the one-line version is that agility is the property that lets you re-read the ruler and act on it.
> **Note:** 1. For long-lived secrets, default to ML-KEM-1024 and ML-DSA-87; reserve the smaller sets for ephemeral or low-value data. 2. Deploy post-quantum key exchange in hybrid with a classical algorithm, never alone. 3. Make algorithm and parameter choices swappable in configuration -- build for the swap you will eventually make. 4. Watch the lattice estimator and the cryptanalysis literature, not the headlines; the real signal is a few bits moving, not a dramatic announcement. 5. Keep a non-lattice backstop in your portfolio -- SLH-DSA for signatures, HQC for key encapsulation -- so a systemic lattice result is a migration, not a crisis [@fips-205] [@nist-ir-8545].
Watch the estimator, not the headlines. The break, if it comes the likely way, will show up first as a revised number in a tool most people never look at. The teams that will migrate calmly are the ones already tracking that number.
These are not the moves of a field in crisis. They are the moves of a field that has learned to live with a believed-hard problem, and to read its ruler honestly.
## 11. Frequently Asked Questions, and a Closing Thought
No. At the standardized parameters, no public attack recovers a key or forges a signature. What is happening is measurement, not breakage: cryptanalysts refine the estimated cost of the best attacks, and the numbers drift. The 2022 MATZOV result thinned the estimated margin of the smallest Kyber set, but even its magnitude is contested, and the block size a real attack needs remains far beyond anything ever demonstrated [@matzov-2022] [@ducas-pulles-2023].
No, and that is the entire reason they were chosen. Shor's algorithm breaks RSA and elliptic curves by finding hidden periodic structure over a commutative group; lattice problems do not expose that structure, and the one explicit bridge to a hidden-subgroup problem lands on the non-commutative dihedral group that Shor's method does not solve [@regev-quantum-2002]. The only known quantum advantage against lattices is a modest speedup of the sieving oracle [@peikert-decade-2016].
Only in the weak, generic sense that it speeds up brute-force search everywhere. Grover turns a cost of $2^{n}$ into $2^{n/2}$, so it effectively halves the exponent of a key search -- a discount the parameter sizes already absorb. It exploits nothing specific to lattices and is not a structural break.
Both standards rest on Module-LWE, so a single lattice-reduction advance debits both at once -- that is the correlation. It is one-directional and unequal: the two schemes use different moduli and ranks, so the same advance erodes them by different amounts, and ML-DSA carries an extra forgery route through Module-SIS that ML-KEM does not share [@fips-204]. The key-encapsulation mechanism, in turn, has its own extra route through decryption failures [@danvers-guo-2019]. Shared spine, not identical schemes.
No. Security bits come from the cost of lattice reduction, not from a larger modulus, and *more* ring structure can *add* attack surface rather than remove it -- an overly large modulus is exactly what makes overstretched-NTRU breakable [@albrecht-bai-ducas-2016]. The standards chose the power-of-two cyclotomic ring because it gives the attacker the least algebraic help [@ducas-mbkz-2025], not because bigger is better.
No. KyberSlash is an implementation timing leak -- a flaw in how specific software computed, not in the mathematics of Module-LWE. It is real and it mattered, but it lives outside this article's structural scope. The empirical sibling, "How ML-KEM Breaks in Real Life," covers that whole family of implementation attacks.
For long-lived data, prefer the higher parameter sets (ML-KEM-1024, a high ML-DSA level) [@fips-203] [@fips-204]. Deploy post-quantum key exchange in hybrid with a classical algorithm so a lattice break is not a single point of failure, build crypto-agility so you can swap parameters or algorithms as a configuration change, and keep a non-lattice backstop such as SLH-DSA or HQC in your portfolio [@fips-205] [@nist-ir-8545].
So return to the question the celebrations skipped. If a quantum computer cannot break ML-KEM and ML-DSA the way it broke RSA, how *would* they break? The answer, assembled piece by piece, is a single sentence: two standards, one lattice, one ruler. They share the Module-LWE spine, and their strength is not proven but measured, on a core-SVP ruler that the field argues about in the open. The likely break is that ruler slipping a few bits at a time as reduction improves -- and because both standards read the same ruler, one slip debits both at once.
The evidence lines up behind that reading. Erosion is not hypothetical: MATZOV already moved the margin once, and the only debate is by how much. The feared quantum collapse remains unrealized -- the best attempt was retracted within days over a bug at Step 9. The structural wildcard, the algebra of the cyclotomic ring, is genuinely unpriced by the ruler, but the newest analysis finds the power-of-two ring gives the attacker no free reduction, and NIST hedged anyway by standardizing code-based HQC.
The verdict is not "broken." It is "believed hard, conservatively measured, and watched closely" -- the same position RSA has long occupied, on a much younger assumption.
Which is why the honest way to end is not with a warning but with a recalibration. If the break comes the likely way, it will not be a morning when the internet stops working. It will be a line in a changelog -- a revised constant in a tool most people never open, moving the ruler a few bits and asking, quietly, whether it is time to turn the parameter dial again.