Two Standards, One Lattice: How ML-KEM and ML-DSA Would Break

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 ^[1] and ML-DSA as FIPS 204 for signatures ^[2]. 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.

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.

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 ^[3]. 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 grid has a catch that makes it useful. Given a "bad" basis, simple questions become brutal.

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 ^[4]. 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 ^[5].

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.

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 ^[6]. 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 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 ^[7]. 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 ^[8]. 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 ^[9]. 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.

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 ^[10]. 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.

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.

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 ^[11]. 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 ^[1]. 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 ^[2]. Same spine, different parameters.

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.

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.

Vadim Lyubashevsky introduced the "with aborts" idea in 2009 ^[12] and made it a trapdoor-free lattice signature in 2012 ^[13]; ML-DSA is its standardized descendant ^{[14] [15]}. 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 ^[20].

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 ^[21]. 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 model originated with the NewHope proposal in 2016 ^[22]. 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 ^[23]; its maintained successor is the tool NIST parameters are checked against ^[24]. ※ 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.

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 ^[25]. 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.

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 ^[27]. 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 ^[23]. 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 ^[28]. 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) ^[29] 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.

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 ^[30].

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.

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$ ^[24]. The public record for a solved shortest-vector challenge, tracked on the SVP Challenge Hall of Fame, stands near dimension 210 ^[31]. 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 ^[32], 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 ^[33].

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 ^[34]; "failure boosting" uses precomputation to hunt for failure-inducing ciphertexts ^[35]; failures cluster, so one found failure makes the next more likely ^[36]; and "directional" boosting exploits that clustering, so the cost is dominated by finding the first failure ^[37].

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$ ^[35]. It is the mirror image of ML-DSA's extra forgery route: real, scheme-specific, and neutralized by the parameter margin, not by luck.

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 ^[38]. 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

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}$ ^[39]. 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 ^[42]. 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 ^[43].

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 ^[9].

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 ^[44]. 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.

Put the three routes on one page and the wildcard sits where it belongs.

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 ^[45], explicitly as insurance against a systemic weakness in lattices ^[46]. 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}$ ^[49]. 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.

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 ^[21]. 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.

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 ^{[1] [2]}. 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 ^[26].

Deploy in hybrid. 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 and the post-quantum toolkit go deeper here; the one-line version is that agility is the property that lets you re-read the ruler and act on it.

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#

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.