A Quantum Algorithm Just Took Aim at Post-Quantum Crypto’s Core
The most consequential result in post-quantum cryptography this month is a preprint that may or may not be wrong. Daniel Simon, a cryptographer at Amazon Web Services, has posted a claimed polynomial-time quantum algorithm for the Dihedral Coset Problem, an abstract puzzle that happens to sit one mathematical reduction away from the lattice problems holding up most of the world’s post-quantum encryption. If the claim survives scrutiny, it’s the biggest development in the field in years. Everything rides on that “if.”
Simon isn’t a random name here. In 1994 he published Simon’s algorithm, the black-box result that showed a quantum computer could be exponentially faster than a classical one, and it directly inspired Shor’s algorithm two years later. When the person who helped start quantum algorithms turns his attention to the math protecting the post-quantum era, cryptographers pay attention.
What Simon is claiming
The Dihedral Coset Problem is a hard relative of the problem Shor’s algorithm demolishes. Shor works because factoring hides inside a well-behaved, abelian group where quantum computers find structure easily. The dihedral group is the nasty case, and for two decades the best tool was Greg Kuperberg’s algorithm, which runs in subexponential time, faster than brute force but far from efficient.
The stakes come from a bridge built by mathematician Oded Regev, who showed that certain lattice problems, the ones cryptographers now rely on, reduce to the Dihedral Coset Problem. Regev’s bridge had a missing plank: it assumed an idealized “oracle” that could solve another hard problem for free.
Simon claims to replace that oracle with a real polynomial-time procedure, one that tolerates a share of faulty samples, and to come out the other side with efficient quantum algorithms for approximate versions of the Shortest Vector Problem and certain Learning With Errors instances. Those are the mathematical foundations of lattice cryptography.
He states it plainly in the abstract of the paper, which he labels a preliminary draft:
“We present a polynomial-time quantum algorithm for the Dihedral Coset Problem (DCP). The algorithm is based on Regev’s polynomial-time reduction of the Dihedral Subgroup Problem (DSP) to the modular subset sum problem, but uses a different technique to erase sample bits without use of a subset sum oracle.”
What’s at stake if it holds
Lattice math is not a niche. Learning With Errors underpins ML-KEM and ML-DSA, the two schemes NIST standardized and the ones governments and companies are now spending years and billions to deploy.
The entire premise of that migration is that no efficient quantum attack on these problems is known. A polynomial-time quantum route to lattice problems would poke a hole in the premise, which is why a transition already underway would suddenly face a harder question.
The reasons to keep your hand off the alarm
Once you read past the abstract, the claim narrows fast. This is a preprint that hasn’t cleared peer review. It analyzes no specific standard and presents no key-recovery attack. It offers no estimate of the qubits, gates, or error-corrected operations an implementation would need, and a polynomial-time algorithm can still be useless in practice if its degree is high or its constants are enormous.
The approximation it reaches, a square-root-of-n polylogarithmic factor, along with the distance between worst-case lattice problems and the average-case instances real schemes use, may never touch the parameters inside deployed Kyber or Dilithium. Weakening one formulation of Learning With Errors doesn’t automatically break the family.
Simon himself confines the claim to the problems and ranges his reductions reach, and says he’s in discussion with lattice specialists including Daniele Micciancio, Vinod Vaikuntanathan, and Thomas Vidick.
Why that last detail should sound familiar
We have run this exact drill before. In April 2024 the cryptographer Yilei Chen posted a polynomial-time quantum algorithm for Learning With Errors, and for about a week it was the only thing the field talked about. Then Hongxun Wu and, independently, Thomas Vidick found a bug in step nine. Chen couldn’t repair it, and the central claim collapsed into a footnote.
Notably, Vidick, who broke the last big lattice claim, is one of the people vetting this one. Extraordinary results against lattice cryptography have a habit of not surviving line-by-line review, and even Chen’s, had it held, wouldn’t have directly broken the NIST standards, the same limit that applies here.
The case for taking it seriously anyway
None of that makes the paper noise. Simon has the pedigree, the Dihedral Coset barrier has stood for twenty years, and a credible attempt to bring it down earns the field’s attention even if the payoff is theoretical rather than a working attack.
A result like this changes how cryptographers price the risk of leaning so heavily on one kind of math, and it strengthens the case for the crypto-agility good security teams already practice. If lattices ever wobble, NIST also standardized hash- and code-based schemes built on different assumptions, and the reason to migrate now doesn’t hinge on this paper being right.
The rational response is neither panic nor a shrug. It’s to let the referees do their work. The good thing about preprint culture is speed: this claim will be validated or punctured in a matter of weeks. Until then, it’s a remarkable “if,” and nothing more.