Daniel Simon Claims a Polynomial-Time Quantum Algorithm for Lattice Problems. And a CRYPTO 2026 Paper Connects It to ML-KEM

August 6, 2026 — Daniel R. Simon, the creator of Simon’s algorithm and a researcher in the Amazon Web Services Cryptography Group, has posted a preliminary draft claiming a polynomial-time quantum algorithm for the Dihedral Coset Problem (DCP). Reductions published over the past two decades connect the DCP to approximate lattice problems and to Learning With Errors, which is what makes the claim consequential for post-quantum cryptography.

“Consequential” is doing careful work in that sentence. The paper has not been peer-reviewed. Several of its load-bearing proofs are presented as sketches. Its final corollary on SVP and LWE parameters rests on personal communications that have not been published. And it contains no attack on ML-KEM (FIPS 203), ML-DSA (FIPS 204), FN-DSA (in development as FIPS 206), or any concrete NIST parameter set.

The bottom line for anyone running a migration program: lattice cryptography faces its most credible theoretical challenge in two decades, and the path from Simon’s claim to the algorithms you are actually deploying is shorter than it looked a week ago, because a separate peer-reviewed result accepted to CRYPTO 2026 supplies the Module-LWE link that used to be the hand-waving step. Nothing standardized is broken. No attack has been costed against any parameter set. I would not pause a single ML-KEM rollout over this. I would look very hard at how much of your migration rests on one branch of mathematics.

I cancelled three meetings today to read this properly. That happens maybe twice a year.

What Simon Claims

Simon’s algorithm targets a problem that has sat at the center of quantum lattice cryptanalysis since 2004, when Oded Regev established a polynomial-time quantum reduction connecting the Dihedral Coset Problem to approximate unique-SVP and related lattice problems. Regev also gave a conditional polynomial-time algorithm for the DCP, but it assumed access to an efficient coherent solver for average-case modular subset-sum instances. No such general polynomial-time procedure is known, so the reduction sat for twenty years as an elegant result with no attack behind it.

Without that capability, the best available quantum algorithm for the dihedral problem was Greg Kuperberg’s 2005 construction, running in subexponential time: 2^O(√log N), roughly 2^O(√n). For polynomial-factor approximate SVP, the best algorithms of either kind, classical or quantum, run in fully exponential time (BKZ and its variants). Quantum computing offered lattice attackers nothing worth having.

Simon’s contribution is a technique that replaces the subset-sum procedure. His algorithm uses Hadamard transforms and a grouping strategy to erase sample bits, while tolerating a faulty sample rate as high as 1/O(log n). Combined with Regev’s reduction and a 2018 improvement by Brakerski, Kirshanova, Stehlé and Wen that tightened the parameter relationship between LWE and an extrapolated variant of the DCP, Simon claims polynomial-time quantum algorithms for:

• Approximate SVP with an approximation factor of O(√n · polylog(n))
• LWE instances with noise parameter α = O(√n · polylog(n))

Subexponential to polynomial is a qualitative change, not an incremental one. It is the difference between “quantum computers do not help against lattices” and “quantum computers solve lattice problems efficiently, given the hardware.”

The Reduction Chain

The connection between an abstract group theory problem and a TLS handshake runs through a chain of reductions that researchers have been building for twenty years. Simon’s claim is the piece that, if correct, energizes the whole chain.

Regev (2004) connected DCP to approximate unique-SVP and related lattice problems. Brakerski, Kirshanova, Stehlé and Wen (2018) connected LWE to a generalized extrapolated-DCP formulation and reduced it to DCP with parameter transformations. Simon claims his polynomial-time DCP solver composes with these to yield polynomial-time algorithms for the lattice problems themselves. The paper’s final corollary, the one stating the specific SVP and LWE parameters, cites Seyoon Ragavan and Daniele Micciancio as personal communications rather than published derivations, so the exact parameter claim has not been independently set down anywhere a reviewer can check it.

The Module-LWE link

Until last week, the honest assessment of the gap between Simon’s claim and NIST’s standards was that plain LWE is not what ML-KEM and ML-DSA use. Both rest on Module-LWE, which carries extra algebraic structure, and the textbook reductions from Module-LWE to plain LWE cost parameters.

That gap is narrower than I described it in my first read of the paper (an hour ago, in case you caught that version), and the reason is a separate piece of work that has already been through peer review. Weiqiang Wen and Jinwei Zheng of Télécom Paris have published “Module Learning With Errors and Structured Extrapolated Dihedral Cosets”, the full revision of a paper accepted to CRYPTO 2026. They prove a quantum polynomial-time equivalence between Module-LWE and a structured variant of the extrapolated dihedral problem they call IP-M-EDCP, and they give a further reduction from IP-M-EDCP to plain EDCP.

Wen is a co-author of the 2018 paper Simon builds on, so this is the same research line continuing, not a coincidence of two groups arriving at the same place. The chain that results looks like this: Module-LWE, to structured EDCP, to EDCP, to DCP, to whatever Simon’s algorithm turns out to be. That is a considerably more direct route to ML-KEM’s underlying assumption than “lattices are lattices.”

Three qualifications keep this from being a proof of anything about deployed schemes. The Wen-Zheng equivalence is proved for search Module-LWE over power-of-two cyclotomic rings with constant module rank, in a specific parameter regime tying the modulus, sample count and Gaussian width together; the authors state in their open problems that their use of Rényi divergence suits search variants and does not extend naturally to decision variants, which is the form most security proofs use. Their reduction runs from Module-LWE into the dihedral world, and composing it with a DCP solver in the other direction at cryptographically relevant parameters is exactly the arithmetic nobody has published. And ML-KEM’s actual error distribution is centered binomial rather than discrete Gaussian, with a fixed and very small sample budget.

What the paper does establish is direction of travel, and the authors are candid about it: they present IP-M-EDCP as a target that “might be easier than EDCP” and explicitly invite cryptanalysts to attack it. They also note that Yilei Chen’s withdrawn 2024 claim was an attempt to solve LWE through a variant of EDCP, and that Bai, Jangir, Kirshanova, Ngo and Youmans presented a quasi-polynomial-time quantum algorithm for EDCP over power-of-two moduli at CRYPTO 2025. Their own summary of the state of play before Simon: “no subexponential-time quantum algorithm in n is known for solving EDCP with parameters enabling a reduction from LWE.” That sentence is the load-bearing assumption under a great deal of deployed cryptography, and three separate research efforts are now pushing on it.

Which Algorithms This Would Touch

If Simon’s result holds and the reductions compose, the consequences separate by mathematical family rather than by vendor or standard.

ML-KEM is the most directly exposed. Its security rests on Module-LWE over the power-of-two cyclotomic ring Z_q[x]/(x^256+1), with module rank 2, 3 or 4. Constant module rank over a power-of-two cyclotomic ring is precisely the setting Wen and Zheng cover, and they say so, calling it “a setting of particular relevance in cryptographic applications.” The bridge is structural rather than incidental. What remains unproven is whether the composed chain preserves parameters through ML-KEM’s specific modulus, noise distribution, sample count and decision formulation, and whether the resulting attack costs anything a machine could pay.

ML-DSA is a step further removed. It uses Module-LWE, so the same bridge applies to part of its foundation, but NIST’s FIPS 204 rests the scheme’s security on SelfTargetMSIS as well. A break of Module-LWE would be extremely serious for ML-DSA. It would not by itself constitute a signature forgery or a signing-key recovery, and anyone reporting it that way is skipping a step that requires its own analysis.

FN-DSA is not implicated by this path. FALCON, the basis for draft FIPS 206, uses an NTRU lattice construction. No published reduction connects the DCP work to NTRU hardness. It needs a separate assessment, and I grouped it with the other two in my first draft of this analysis, which was wrong.

Unstructured lattices are not the safe harbor here. FrodoKEM, which ANSSI names as an acceptable conservative alternative KEM precisely because it avoids algebraic structure, is built on plain LWE. Plain LWE is what Simon’s corollary addresses most directly. The conservative choice sits closest to the claimed result, which is an uncomfortable inversion of the usual advice and worth sitting with for a moment.

Nothing hash-based or code-based is touched. SLH-DSA (FIPS 205) rests on hash function security. LMS and XMSS (SP 800-208) likewise. HQC, the code-based KEM NIST selected in March 2025 as the non-lattice backup to ML-KEM, rests on coding-theory hardness. AES, SHA-2 and SHA-3 are unaffected.

My Analysis

I need to state something up front. I am not a theoretical cryptographer. I have 30 years of cybersecurity experience, I have spent two decades tracking the quantum threat to cryptography, and I have read this paper carefully. The machinery in Lemmas 3 and 4, the pairwise independence arguments, the amplitude concentration bounds, the conditioning analysis, sits at the boundary of what I can independently verify. I am waiting for assessments from Micciancio, Peikert, Regev, Ducas and the rest of the lattice community, the same way I would wait for a structural engineer’s report rather than pronounce on a bridge from my own look at it.

What I can do is assess the paper’s credibility, identify where it is most vulnerable, place it against the other lattice cryptanalysis claims I have covered this year, and draw the strategic conclusions my readers need this week.

My working assessment: a low-confidence theorem with a potentially systemic consequence, no operational exploit, and immediate architectural relevance. That is a material emerging cryptographic risk. It is not a confirmed break, and I would push back hard on anyone selling it as one.

Why Simon’s paper is not the usual lattice scare

PostQuantum.com has covered several lattice cryptanalysis claims over the past year. I debunked a viral Seoul National University paper in May that argued lattice-based PQC has “fundamental limitations.” I analyzed the HAWK attack paper in June, which rested on unverified heuristics that a former NIST cryptographer subsequently identified as flawed. Credulity is not my failure mode on this topic.

Daniel Simon’s 1994 algorithm was the first demonstration of an exponential quantum speedup for an oracle problem. It circulated from 1993 and directly catalyzed Peter Shor’s development of his factoring and discrete logarithm algorithms in the same year. Shor’s algorithm reshaped cryptography and created the field of post-quantum security. This is not a graduate student posting an unchecked preprint at 2 a.m.

The acknowledgments carry information too. Simon thanks Daniele Micciancio, one of the world’s foremost lattice cryptographers. He thanks Vinod Vaikuntanathan, who received the 2022 Gödel Prize for foundational work on fully homomorphic encryption from LWE. He thanks Thomas Vidick, a leading quantum complexity theorist who was among the researchers who found the flaw that ended the last comparable claim, Yilei Chen’s 2024 ePrint on quantum algorithms for lattice problems, withdrawn within days. He thanks Seyoon Ragavan and Sanketh Menda, both working at the intersection of quantum algorithms and lattice cryptography.

Precision about what that does and does not mean: thanking someone for “immensely useful discussions and suggestions” is not that person endorsing the proof. None of the acknowledged researchers has published a statement confirming the result. Simon’s record makes the paper impossible to wave away. It does not lower the standard of proof by a single line.

Four places the proof could fail

The paper is labeled “Preliminary Draft” and several critical proofs are sketches. That label is a signal of intellectual honesty about the work’s current state, and it is also a warning about what has and has not been done.

The first vulnerability is the core algorithmic innovation, which relies on probabilistic arguments about the uniformity of quantum state distributions. Lemma 4, establishing that the amplitudes for different values of h* are approximately equal, depends on pairwise independence of subset sums and a balls-in-bins concentration argument. Lemma 3 attempts to establish a “well-behaved” condition (Definition 1) by arguing that pairwise independence of phases makes the amplitudes roughly normally distributed. Whether Lemma 3 delivers the required amplitude bounds after conditioning on the preceding measurements is the most consequential open question in the paper, and Simon himself flags the risk that very large, mutually canceling amplitudes could magnify small distribution differences. This is the precise spot where quantum cryptanalytic claims usually go wrong: a classical counting argument controlling a coherent superposition across multiple measurement and conditioning steps.

The second is Lemma 1, which establishes that the algorithm produces enough qualifying groups with constant probability using an injective mapping from bad to good measurement outcomes. The proof is explicitly a sketch. Reviewers will need to confirm that the mapping preserves measurement probabilities across the full superposition rather than merely the formal phases.

The third is the degree of the polynomial. The construction collects Q = kn^(c+1) DCP samples and later requires c ≥ 12, so an n^13 term appears before recursion, repetitions, reversible arithmetic, state preparation and fault-tolerant overhead enter the picture. Substituting 768 into that expression and reporting the result as the cost of attacking ML-KEM-768, which several early commentaries did, has no basis in the text: the paper carries no parameter translation through the reduction chain, and its n is not the NIST parameter-set label. On r/crypto, one commenter put the general point well, calling the result “technically polynomial, but with such crazy polynomial degrees that it isn’t practical in reality.” Worth remembering, though, that once a problem lands in BQP, later researchers often grind the exponent down. The asymptotic discovery would matter even if Simon’s own construction never becomes an implementation.

The fourth is the final corollary itself, resting partly on those two personal communications. There is also a parameter question I cannot settle and have raised with people who might: the paper states an LWE noise parameter α = O(√n · polylog(n)), while the conventional normalized LWE error parameter lives in the interval (0,1), which is the definition the 2018 Brakerski et al. paper uses. For growing n, √n · polylog(n) exceeds 1. That suggests a missing reciprocal, an unstated inverse-noise convention or a normalization step left out of the draft. Until the author clarifies, the cryptographic range of the LWE claim is ambiguous, and ambiguity at exactly that point is not a small thing.

Verification will take months, not days.

Community reaction so far

As of publication, the canonical ePrint record for 2026/1591 shows the paper received August 3 and approved August 6. None of the acknowledged researchers has published a formal assessment, which is what you would expect for a result of this complexity and is a signal in neither direction.

Daniel J. Bernstein has posted about it: “If [it] collapses upon examination, lattice-based cryptographers will say ‘See, we dodged another bullet’; but aren’t all the bullets more than a bit terrifying? Use the largest parameters you can afford; keep the ECC seatbelt; keep investing in alternatives.” Characteristically, that is the right advice whether or not this particular proof holds.

The initial r/crypto assessment mirrors my own: credible author, trusted record, heuristic counting arguments that may not be sound.

What stays the same

Even if Simon’s proof is correct in every detail, several things do not move.

The CRQC hardware timeline does not shift on the strength of this paper. Simon’s algorithm, like Shor’s, needs a fault-tolerant quantum computer to run on. The engineering problems I track in the CRQC Quantum Capability Framework, including quantum error correction, below-threshold operation, magic state production, decoder performance and engineering scale, are indifferent to an algorithmic advance. (An algorithmic advance can change the resources a future machine would need for a specific attack. This paper offers no circuit-level analysis from which anyone could draw that conclusion, which is why you will not find a qubit count in it or in this article.)

The Harvest Now, Decrypt Later exposure of classical cryptography is unchanged. Organizations that have not moved to any form of post-quantum key establishment face the same HNDL problem from Shor’s algorithm today that they faced yesterday. Freezing an ML-KEM rollout to wait out this debate would trade a known, dated, quantified exposure for protection against a hypothetical failure of the replacement. That trade is bad arithmetic.

Hybrid is not the hedge people think it is

Here is where I want to correct a comfortable assumption, including one I have let stand too easily in my own writing.

Classical-plus-post-quantum hybrid deployment, an ML-KEM and X25519 TLS construction for instance, protects you if either component holds. Against a classical adversary who somehow breaks ML-KEM, the X25519 layer holds. That is real, and it is why BSI and ANSSI have pushed hybrid so consistently, and why the European Cybersecurity Certification Group’s guidance says LWE-based mechanisms should not be used standalone.

But think about the adversary this paper describes. Running Simon’s algorithm requires a large fault-tolerant quantum computer. The same machine runs Shor’s algorithm against X25519 without breaking stride. An adversary capable of exploiting a lattice break is by construction an adversary who has already retired your classical seatbelt. Classical hybrid buys migration time and protects against near-term implementation failures, which is a genuinely good reason to run it. It is not insurance against the specific scenario in this paper.

The insurance against that scenario is diversity of mathematical family among your post-quantum algorithms: hash-based signatures alongside lattice signatures, a code-based KEM you have actually tested rather than one you have read about. Very few organizations have built that. Most PQC programs I see are, in effect, single-assumption bets with a classical seatbelt attached.

Crypto-agility, again

This paper, whether or not the proof holds, is the strongest practical argument yet for why crypto-agility matters more than any individual algorithm choice.

I have been making this case for years, in this blog, in Quantum Ready, in every advisory engagement, and last week in the context of AI security. The pattern keeps repeating. Bernstein’s ML-DSA key recovery in under a second. The HAWK cryptanalysis. Regulatory fragmentation across jurisdictions. Now a credible, unverified polynomial-time quantum claim against lattice assumptions, with a peer-reviewed paper closing the gap to Module-LWE. Each of these is individually manageable. The sequence is the message: crypto-agility is an architecture problem, not a library swap.

Several jurisdictions anticipated this scenario. Germany’s BSI has consistently pushed hybrid deployment and keeps non-lattice alternatives on its acknowledged list. France’s ANSSI strongly recommends hybridization during the transition for products needing long-term protection. NIST built the backup pipeline deliberately, selecting HQC in March 2025 as a code-based alternative to ML-KEM and advancing nine additional signature candidates to a third evaluation round in May 2026, several of them non-lattice: FAEST, MAYO, SQIsign, SDitH and others. The pipeline exists for exactly this contingency. The open question is whether it moves fast enough if the contingency arrives.

The United States took a different path for national security systems. NSA’s CNSA 2.0 permits only ML-KEM-1024 and ML-DSA-87 for general key establishment and signatures (plus LMS and XMSS for firmware signing), does not require hybrid deployment, and excludes SLH-DSA. If Simon’s result eventually produces concrete attacks on Module-LWE at deployed parameters, CNSA 2.0 estates without an independently surviving component would need substantial reassessment, and the firmware-signing carve-out would suddenly look like the most far-sighted line in the document.

What should happen next

The cryptographic community needs three things, in order.

Rigorous independent verification comes first. The researchers best placed to assess the proof are presumably reading it now. The four questions above are where I would start: the amplitude concentration bounds, the injective mapping argument, the unpublished corollary reductions and the α parameter convention. A fifth belongs on the list now, and it is the one nobody has done: composing Wen-Zheng with the DCP work explicitly and showing whether the parameters still hold at anything resembling ML-KEM-768.

Second, if the result shows signs of holding, NIST should assess whether the HQC timeline and the non-lattice signature evaluation should accelerate. Waiting until 2027 for a code-based KEM standard is a comfortable schedule under one set of assumptions and an uncomfortable one under another.

Third, organizations mid-migration should keep migrating. Deploy hybrid where you can. Put SLH-DSA into signature planning alongside ML-DSA rather than as a footnote. Treat lattice-only dependence as a concentration risk and write it into your risk register as one, with an owner and a review date. Make sure the protocols, identities and key-management infrastructure around your algorithms can accept a swap without a rebuild, because that, and not the choice between ML-KEM and HQC, is what determines whether the next result like this one costs you a quarter or three years.

Anyone using this paper to argue for delaying PQC migration is repeating the error made with the Seoul National University paper: confusing uncertainty about one algorithm family with uncertainty about the need to act. The regulatory deadlines, the insurance requirements, the client expectations and the HNDL exposure are all still running. Those clocks do not pause for academic debate.

Looking forward

If the core proof survives review and the reductions compose, this becomes one of the most important developments in quantum cryptanalysis since 1994, with the researcher whose work enabled Shor’s breakthrough producing its lattice-cryptography counterpart three decades later. That is a remarkable symmetry, and it is also a sentence I am writing with heavy conditional load.

Getting there requires more than validating the DCP algorithm. Researchers must confirm the lattice and LWE parameter reductions currently resting on personal communications, resolve the noise-parameter question, carry the Wen-Zheng equivalence and the DCP result through one composed argument at cryptographically meaningful parameters, and establish whether the resulting algorithms cost anything a real machine could pay.

Until that work is done, there is no basis for an emergency retreat from ML-KEM or ML-DSA, and I have not changed a single recommendation I have given a client this year. What has changed is my confidence interval on how long today’s algorithm choices will remain today’s algorithm choices. The durable asset was never any one lattice construction. It is the ability to replace it.