The claimed polynomial-time quantum algorithm for the dihedral coset problem has been refuted. Aparna Gupte (MIT), Seyoon Ragavan (Google Quantum AI and MIT), and Mark Zhandry (Google Quantum AI and Stanford) posted ePrint 2026/1693, a formal proof that the algorithm in ePrint 2026/1591 cannot extract the secret it targets. The authors are explicit that this goes beyond finding an error in the original analysis. They show the algorithm itself cannot work, regardless of how it is analyzed.
When the claim appeared, we assessed it as unconfirmed and argued that the operational conclusion holds in either direction: organizations need a cryptographic inventory and the ability to change algorithms at reasonable cost, because results like this will keep arriving. The refutation settles this instance and adds detail worth understanding.
What the refutation shows
The dihedral coset problem matters because of a 2004 reduction by Oded Regev (SIAM Journal on Computing): an efficient quantum algorithm for it would yield efficient quantum algorithms for the lattice problems underlying ML-KEM and ML-DSA. Regev’s own procedure produces a quantum state alongside classical measurement labels, and it needs a subset-sum oracle, consuming those labels in full, to finish the job. No one knows how to build that oracle efficiently. The claimed algorithm followed Regev’s opening steps and then took a different route that used only a small summary of the labels.
The refutation proves that the different route is closed. Its main theorem states that any algorithm keeping only a small digest of each classical label, rather than the full labels, can guess the target bit of the secret with at most an exponentially small advantage over random guessing. Discarding even slightly more than a logarithmic number of bits per label is already enough to hide the secret. The result is information-theoretic, which means the retained data no longer contains the secret at all. No later computation, however clever, can recover information that is absent from its input.
The claimed algorithm falls inside this theorem because its summaries can be reconstructed, up to negligible error, from roughly the top third of the bits of each label. The authors also close the procedural escape routes. Delaying the measurement of the labels until the end changes nothing, because the measurement commutes to the start. Repeating the procedure to amplify a tiny advantage fails on a cost argument: either the final guessing advantage stays exponentially small, or the expected number of repetitions grows exponentially.
What it leaves open
The theorem constrains one family of approaches. It says any algorithm following Regev’s template must make substantial use of the full classical labels in its final stage. It does not prove the dihedral coset problem hard, and it does not prove lattice problems hard. The authors write that variants might step outside the formal scope of their theorem, but they expect such variants to fail for the same underlying reason, and they know of no plausible repair.
Read as a structural result, this is favorable for the lattice-based standards. The known route through this template requires exactly the resource, a subset-sum oracle over the full labels, that has resisted efficient construction since 2004. Confidence of this kind is rare and worth recording accurately: one class of attacks is now provably closed, and the general question remains open.
How it was verified
The claim was posted on July 31, and the refutation addresses its August 11 revision. The refutation followed within days of that revision and ships with a Lean 4 formalization, machine-checkable code that verifies the main results. The acknowledgments thank Daniel R. Simon, the original author, for discussions, so the review happened with his participation rather than around him. Seyoon Ragavan, a co-author of the refutation, appears in the original draft’s acknowledgements and as one of its two personal-communication citations, which is where we had noted the scrutiny would most likely come from. The authors also disclose that the generalized theorem emerged in conversation with an AI model and that the same tools produced the formalization, with the authors accountable for correctness. Review cycles for cryptographic claims are getting faster, and machine-checked proofs are becoming part of how disputes end.
The operational reading
Between the claim and the refutation there was a window of several days in which the responsible question for a security team was one of scope: which of our assets rely on lattice assumptions as their only post-quantum protection. Answering that question requires an inventory of deployed cryptography that can be queried by algorithm family. A CBOM in CycloneDX 1.6 format supports exactly that query, and [PQ]probe produces one with every scan.
The conclusion from the first post is unchanged by the outcome. The review cycle for this claim ran in days, while algorithm migrations run in years, so planning has to assume more such claims will arrive and cannot pause while each one resolves. The organizations in the best position during this window were the ones that could answer the scoping question the same day the claim was posted.
Sources:
- Gupte, Ragavan and Zhandry, refutation of ePrint 2026/1591
- Simon, A Polynomial-Time Quantum Algorithm for the Dihedral Coset Problem
- Lean 4 formalization of the refutation
- Regev, Quantum Computation and Lattice Problems, SIAM Journal on Computing, 2004