Simon Claims Polynomial-Time DCP Quantum Algorithm
Cookie policy
Quantum Security & PQC
Daniel Simon Claims a Polynomial-Time Quantum Algorithm for Lattice Problems. And a CRYPTO 2026 Paper Connects It to ML-KEM
Marin Ivezic
Follow on X
Send an email
August 6, 2026<br>15 minutes read
Table of Contents
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...