Simon Claims Polynomial-Time DCP Quantum Algorithm

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.

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.

Update, August 10: Daniel Apon, who has been the most active independent verifier of the proof, has published his assessment on LinkedIn: “I don’t believe Simon’s DCP-LWE algorithm is correct. Lemma 3 is clearly false. After significant effort, I don’t see how to repair the analysis.” His formal paper “The Search for Simon” proves the generic proof strategy requires a new theorem he calls AQSE, and concludes it has no local repair. Apon’s personal assessment goes further than his paper’s formal conclusion, which leaves open the possibility that Simon’s specific arithmetic construction could succeed with a new theorem. Other participants in the verification, including Bernstein, Kirshanova, and Simon himself, have not made equivalent statements. This is a significant negative signal from a qualified expert but not yet a community consensus.

The proof has two confirmed problems, both in the places I flagged as most vulnerable.

Lemma 3 has a confirmed proof gap. Apon identified a failure of the pairwise independence argument, attempted to write a fix, and reported: “I take back my comment about knowing how to fix the issue I found with Lemma 3 (failure of pairwise independence). Maybe someone else has repaired it and I need to read, but I tried writing up a proof fix and got stuck; still working.” The core issue: the proof treats coherent common-sign amplitude blocks as though their members had independent signs, but under the Born-weighted distribution that the algorithm actually uses, the A/B partition, the block multiplicities, and the sampling law are all coupled. Multiple participants have proposed alternative constructions. Simon acknowledged the gap and indicated he is working on a fix: “FWIW, I believe the approach you describe there is along the lines that I was planning to use to fix the lemma…” As of this writing, Apon’s assessment stands: “Lemma 3 is still not patched that I can tell.”

Apon has since formalized this analysis in a paper titled “The Search for Simon”, which defines the missing piece as an Adaptive Quantum Subspace Energy (AQSE) theorem and proves that the generic proof strategy has no local repair: zero-group selection alone cannot justify treating the remaining mask bits as a uniform independent Fourier variable. The paper is deliberately conditional: Simon’s specific arithmetic construction could still succeed if a new AQSE theorem is proved for it, but the fix cannot come from patching the existing Parseval argument.

Lemma 4 has what appears to be a structural defect rather than a gap. A detailed analysis circulating in the verification group identifies a specific substitution on page 14 that replaces a doubly-cancelling signed sum with a non-negative quantity, making the branch amplitude ratio positive by construction. The algorithm needs this ratio (call it ρ) to be positive for the extracted bit to be correct. The catastrophic failure mode is ρ ≈ -1, which would cause the algorithm to return the wrong bit with certainty, and repetition would make it worse rather than better. The proof as written cannot detect this case, because its conclusion takes the form 1 ± ε, which is structurally incapable of expressing a negative ratio. The analysis concludes: “The proof of Lemma 4 does not prove Lemma 4. This requires no computation to verify; it can be read off the page.” Kirshanova, working through the proof independently, reported a convergent finding from a separate AI-assisted analysis: “it potentially found a bug in Lemma 4.”

Lemma 1 (the injective mapping) remains unproved as written, but Bernstein calls it intuitive: “I agree with @SamJaques that lemma 1 feels intuitive even if it’s still not proven; would be a really weird conspiracy of the subset sums otherwise.”

Two observations from Kirshanova carry particular weight given her role as a BKSW co-author. She notes that the connection to LWE is “underselling the paper”: if correct, the algorithm solves worst-case unique-SVP, which is harder than the LWE instances used in cryptography. She also observes that Simon’s claimed tolerance for noisy samples “is irrelevant, it’s never used in the paper,” since the existing reductions provide polynomially many noiseless samples. Both observations, if they hold, change how the result should be understood. The first makes it bigger in scope than the paper’s own abstract claims. The second simplifies the analysis but does not rescue the proof gaps.

Apon raises a practical point that matters regardless of whether the proof can be repaired: even granting the algorithm works as claimed, the sample complexity at the paper’s stated exponent (c ≥ 13, yielding an n^13 term) means the attack cost would exceed the target security levels of deployed parameter sets. Bernstein draws an analogy to the history of primality testing: “the original exponent of deterministic poly-time primality testing was 12 with a painful proof, then became 10.5 with an easier proof, then 6 with more work.” A correct algorithm with an impractical first proof is a known pattern in complexity theory. Apon agrees the constant is likely to fall if the asymptotics are verified: “I don’t expect an arbitrary large-ish constant 10 or 13 or 14 to hold if the asymptotics are verified.”

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 is now underway, and the early results are mixed in exactly the way one would expect for a preliminary draft from a serious researcher: the algorithm’s design is being taken seriously, but the proof has real gaps that may or may not be repairable. The researchers best placed to settle the question are the ones currently working on it. The four questions I flagged above are where they started, and two of them have already produced confirmed findings. A fifth belongs on the list now: 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.