Daniel R. Simon, a researcher in the Amazon Web Services Cryptography Group, has claimed a polynomial-time quantum algorithm for the dihedral coset problem (DCP), which researchers have linked through published proofs to the lattice mathematics behind NIST’s main post-quantum standards. The International Association for Cryptologic Research lists the paper on its Cryptology ePrint Archive as a preprint received on August 3, 2026.
The paper has not been peer reviewed. In it, Simon described no attack on ML-KEM (CRYSTALS-Kyber), ML-DSA (CRYSTALS-Dilithium), or any NIST parameter set and gave no estimate of the qubits or operations an attack would need.
In 1994, Simon devised the quantum algorithm now known as Simon’s algorithm. In a polynomial-time algorithm, the running time grows no faster than a fixed power of the size of the problem. According to the archive’s description, posted papers “did not undergo any refereeing process other than verifying that the work seems to be within the scope of cryptology and meets some minimal acceptance criteria.”
The problems involved
A lattice is a regular grid of points in a space of hundreds of dimensions. In the shortest vector problem (SVP), a solver must find the nonzero grid point closest to the origin. In approximate versions, a solver may return any point within a stated factor of that distance.
In Learning With Errors (LWE), a solver must recover a secret from linear equations, each with a small random error added. ML-KEM is based on Module-LWE, a structured version of LWE in which the unknowns are polynomials. ML-DSA is based on Module-LWE and a related problem called Module-SIS.
In the DCP, a quantum computer must find a hidden amount from many quantum states, each a superposition of two numbers that differ by that amount. Oded Regev showed, in work first presented in 2002, that a quantum computer with an algorithm for the DCP could use it to solve a version of SVP. A reduction of this kind is a proof that an efficient method for one problem can be turned into an efficient method for another.
Simon wrote that Regev’s polynomial-time algorithm for the dihedral subgroup problem, a closely related task, “relies on a subset sum oracle,” a subroutine assumed to solve a problem called subset sum. In subset sum, a solver must find which numbers in a list add up to a given total.
The best previously known quantum algorithm for the dihedral coset problem, Simon wrote, was Greg Kuperberg’s, posted in 2003. It takes subexponential time, more than any polynomial but less than exponential.
What Simon claims
Simon wrote that his algorithm follows Regev’s reduction of the dihedral subgroup problem to modular subset sum “but uses a different technique to erase sample bits without use of a subset sum oracle.” Combined with Regev’s reduction of lattice problems to the DCP, as improved in 2018 by Zvika Brakerski, Elena Kirshanova, Damien Stehlé, and Weiqiang Wen, the algorithm would lead to polynomial-time quantum algorithms “for various lattice problems,” he wrote.
In a corollary, Simon applied the claim to approximate SVP within a factor of about the square root of the lattice dimension, up to polylogarithmic factors. He also applied it to LWE instances whose noise parameter grows at the same rate.
Proofs and sources in the draft
Simon labeled the paper a “Preliminary Draft” on its title page and dated it July 31. In the version available on August 6, he marked the proofs of three lemmas and one corollary as sketches. He stated running times only as polynomials in the problem size, with no figures for any key size.
For the corollary that states the SVP and LWE parameters, Simon cited personal communications from Seyoon Ragavan and Daniele Micciancio, not published proofs. He thanked Sanketh Menda, Micciancio, Ragavan, Vinod Vaikuntanathan, and Thomas Vidick for “many immensely useful discussions and suggestions.” Simon is the paper’s only author.
Earlier claims and a related paper
In April 2024, Yilei Chen of Tsinghua University posted a claimed polynomial-time quantum algorithm for LWE to the same ePrint archive. Eight days later, Chen wrote that one step contained a bug he did not know how to fix. He credited Hongxun Wu and, independently, Thomas Vidick with finding it.
In a separate paper accepted to the CRYPTO 2026 conference, Weiqiang Wen and Jinwei Zheng of Télécom Paris showed that, for a quantum computer, Module-LWE is as hard as a structured version of the extrapolated DCP, a relaxed form of the problem.
Standards based on other mathematics
On August 6, cryptographer Daniel J. Bernstein wrote that even if the paper “collapses upon examination,” users should “use the largest parameters you can afford” and “keep investing in alternatives.”
NIST’s SLH-DSA (SPHINCS+) signature standard is based on hash functions. In March 2025, NIST selected HQC, an algorithm built on error-correcting codes, as a backup to ML-KEM. NIST said it planned to finalize an HQC standard in 2027.
Update, November 12, 2026: On August 15, Aparna Gupte of MIT, Seyoon Ragavan of Google and MIT, and Mark Zhandry of Google and Stanford posted a paper titled “The ePrint:2026/1591 Quantum Algorithm Does Not Solve DCP.” Simon has since revised his draft several times, most recently on November 3, and added a note in October responding to that paper. He has not withdrawn the draft, and its abstract still claims a polynomial-time algorithm.
