MIT and Google Cryptographers Refute Daniel Simon's Claimed Quantum Attack on the Lattice Problems Behind ML-KEM
Quentir Defense Monitor
Evidence-based insights for quantum defense and security. Published by Quentir Systems LLC · September 2, 2026.
For three weeks in August 2026, the mathematics underneath the world's newest encryption standards sat under a serious question, raised by one of quantum computing's founding figures. Daniel Simon, the cryptographer whose 1994 discovery of Simon's algorithm helped set Peter Shor on the path to his factoring algorithm, and who now works at Amazon Web Services, posted a preprint on the Cryptology ePrint Archive claiming a polynomial-time quantum algorithm for the dihedral coset problem. Reductions built over two decades connect that problem to the lattice problems underneath ML-KEM, the key-encapsulation standard that federal agencies, defense ministries and much of the commercial internet are migrating to right now. If the algorithm worked as claimed, the consequences reached far beyond one paper.
On September 1 the question closed. Aparna Gupte of MIT, together with Seyoon Ragavan of Google Quantum AI and MIT and Mark Zhandry of Google Quantum AI and Stanford, published the final revision of a proof that the algorithm does not solve the problem. Their result is stronger than a hole in the analysis. They show the algorithm itself, and every algorithm built along the same lines, provably extracts nothing usable about the secret it is meant to recover. Simon's own paper now carries a note acknowledging the refutation and saying he is evaluating it.
For a defense reader this is two stories in one. An offensive cryptanalytic capability that would have ranked among the most consequential of the decade failed to materialize, and every migration program that had quietly started asking whether to pause got its answer in under a month. It is worth walking through what was claimed, what was proved, and what a buyer of post-quantum cryptography should carry away from three weeks of cryptanalysis conducted entirely in the open.
What ePrint 2026/1591 Claimed: A Polynomial-Time Quantum Route from the Dihedral Coset Problem to Lattice Secrets
The dihedral coset problem is a puzzle from the hidden-subgroup family that quantum algorithms have circled since the 1990s. An algorithm receives quantum states that each encode a hidden secret in a scrambled form, and the task is to recover the secret from many such samples. The strongest known quantum approach, published by Greg Kuperberg in 2003, runs in subexponential time, which is far too slow to threaten cryptography at deployed parameters. The problem has resisted every attempt at a polynomial-time solution for a quarter century, and a good deal of modern cryptography leans on that resistance.
The lean comes through a chain of reductions. In 2003 Oded Regev showed that an efficient dihedral coset solver of the right kind yields an efficient quantum algorithm for the unique shortest vector problem on lattices, and later work extended the bridge toward the learning with errors problem, the foundation under most deployed lattice cryptography. Simon's preprint claimed a polynomial-time quantum algorithm for the dihedral coset problem that tolerates a modest rate of faulty samples, and stated plainly what would follow: combined with Regev's reduction, polynomial-time quantum algorithms for approximating short lattice vectors and for solving learning with errors instances with comparable parameters.
FIPS 203, finalized by NIST in August 2024, standardizes ML-KEM, a key-encapsulation mechanism whose security rests on the module learning with errors problem, and NIST describes it as secure against adversaries who possess a quantum computer. The NSA's CNSA 2.0 suite requires ML-KEM and the lattice signature ML-DSA for national security systems, allied governments have aligned their own guidance, and browser vendors and cloud providers ship hybrid ML-KEM key exchange today. A polynomial-time quantum attack on the underlying lattice problems, even one still needing years of engineering before any hardware could run it, would have forced the entire migration to be re-planned around code-based and hash-based alternatives. Coming from the author of one of quantum computing's founding algorithms, the claim could not be waved away.
The Gupte, Ragavan and Zhandry Proof: Discarded Fourier Labels Leave Key Recovery at Random Guessing
The refutation is short, and its central idea is legible without the formalism. Along its way, Simon's algorithm produces classical measurement outcomes, called Fourier labels, and keeps only about the most significant third of the information they carry, discarding the rest as noise to be managed. Gupte, Ragavan and Zhandry prove that the discarded portion is load-bearing. Their information-theoretic argument shows that once those bits are gone, the algorithm's output carries so little correlation with the hidden secret that it cannot predict even the secret's least significant bit noticeably better than a coin flip. An attack that ends at a coin flip has not extracted a key.
The proof's breadth is what makes it decisive rather than merely corrective. The authors show the failure applies to a much broader class of algorithms than Simon's specific construction: any approach following the template of Regev's reduction that does not make extensive use of the classical Fourier labels during its uncomputation stage runs into the same wall. There is no patch, no better error analysis, no cleverer parameter choice that rescues this design. Simon revised his preprint to acknowledge the no-go result and wrote that he is in the process of evaluating it. As of this writing no counter-argument has appeared, and the specialist consensus reflected in the technical press covering the exchange treats the question as settled.
Quantum pillar: post-quantum cryptography (cryptanalysis of PQC candidates). Use posture: defensive. Technology readiness: TRL 2 of 9. The claimed attack existed only as an algorithm worked out on paper, and the new impossibility proof removes even that footing, so no functioning quantum attack on deployed lattice encryption exists at any rung of the ladder and migration programs keep their basis.
What a Working Dihedral Coset Attack Would Have Given an Adversary, and What Its Failure Gives the Defender
Read as capability, the August claim described the raw material for retrospective decryption at scale. Intelligence services on several sides already collect encrypted traffic they cannot read, on the expectation that a future machine will open it. A polynomial-time lattice attack would have extended that harvest-now strategy past the migration itself: traffic protected by ML-KEM, the very fix agencies are deploying against the harvesting threat, would eventually have been readable too, and lattice-based signatures would have offered a forgery path into software update chains and command authentication. Between the paper and any such capability stood years of further work, extension of the result to deployed module-lattice parameters, and a fault-tolerant quantum computer that does not exist. The episode still shows how algorithm-level risk arrives: as mathematics first, in public, with the engineering question opening only afterward.
The refutation hands the defender three concrete things. First, the security case for continuing the migration is intact, and a program office that held its schedule through August needs no revision to its basis of estimate. Second, the value of crypto-agility stopped being hypothetical for three weeks. Organizations that maintain a cryptographic inventory and a rehearsed algorithm-rollover path spent August pricing a contingency; organizations without one spent it discovering they could not even scope the question. The next serious claim may survive review, and the difference between those two postures is the difference between a controlled swap and a crisis program. Third, hybrid key establishment, which wraps ML-KEM together with a classical elliptic-curve exchange, showed its worth as insurance against exactly this category of surprise.
How a Program Office Should Read Three Weeks of Open Cryptanalysis
The sources establish a precise sequence. A serious polynomial-time claim against the dihedral coset problem went up in early August from a cryptographer of undisputed standing. Within days, researchers at MIT, Google Quantum AI and Stanford began probing it, and by September 1 they had published an impossibility proof covering the whole design family, with the author engaging openly. The sources do not establish any weakness in ML-KEM, any working attack on lattice cryptography, or any reason to slow a migration. They equally do not establish permanent immunity, because no reduction-based argument can promise that a genuinely new idea will fail the same way.
What a buyer can rely on is the pipeline the episode exposed. The strength of standardized cryptography has never rested on any single proof holding forever; it rests on every serious attack being published, examined and answered in the open, where a defense ministry in Canberra reads the same refutation as a vendor in Munich. That pipeline just processed a challenge from one of the field's founders in three weeks. The lattice problems under ML-KEM have now survived another attempt from an inventor of the very tools used to attack them, and the practical guidance that follows is unglamorous: keep the inventory current, keep the rollover path rehearsed, and treat published cryptanalysis as a standing input to procurement rather than a reason for alarm or for comfort.
Sources
Primary source: Aparna Gupte (MIT), Seyoon Ragavan (Google Quantum AI, MIT) and Mark Zhandry (Google Quantum AI, Stanford), 'The ePrint:2026/1591 Quantum Algorithm Does Not Solve DCP,' Cryptology ePrint Archive, final revision September 1, 2026. Other material: Daniel R. Simon's dihedral coset preprint (August 2026); NIST FIPS 203 (August 2024); Oded Regev's 2003 reduction; hwupgrade.it's September 1 report.