Daniel R. Simon, a cryptography researcher at Amazon Web Services (AWS), claims to have filled a gap that has stood since 2002, when Oded Regev demonstrated a connection to lattice problems. The target is the Dihedral Coset Problem (DCP), and Simon reportedly presents a procedure that solves it in polynomial time on a quantum computer. Because existing reductions link DCP to lattice problems, a valid proof would also affect part of the hardness underpinning lattice-based cryptography. However, this is not research that implements an attack on any standardized cryptosystem. The paper is a preprint that has only just been made public, and the proof itself is the first thing that needs to be verified.
The Polynomial-Time Gap That Remained in DCP
Simon's paper, "A Polynomial-Time Quantum Algorithm for the Dihedral Coset Problem," was received by the IACR Cryptology ePrint Archive on August 3, 2026, and approved on August 6 of the same month. Simon is the sole author, affiliated with AWS. It is classified as a preprint, and no DOI has been assigned. There is no indication that it has been accepted by a peer-reviewed journal or conference, and given how recently it was published, there are no reports yet of independent reproduction or verification.
In DCP, one receives multiple quantum states that each embed the same unknown value s, and the goal is to recover s from them. Each input is, roughly speaking, a superposition of |0,x⟩ and |1,x+s⟩. Simon's claim is that a polynomial number of these quantum samples—relative to the input size—can be used, and the whole process can be handled in polynomial time. This is not a study specifying a fixed, empirically measured number of samples; it is an asymptotic analysis discussing how the requirement grows as the input size increases.
The previous leading result was a subexponential-time quantum algorithm presented by Greg Kuperberg in the SIAM Journal on Computing. That 2005 paper (DOI: 10.1137/S0097539703436345) bounded both time and query count to 2^{O(√log N)}. More recently, Shi Bai and colleagues, in a 2025 ePrint preprint, presented an algorithm solving the extended DCP (eDCP)—defined modulo a power of two—in quasi-polynomial time; that work was later included in PKC 2026. What sets Simon's preprint apart from prior work is that it claims polynomial time for DCP itself.
Removing the Subset-Sum Oracle
The key technical challenge is to strip away unwanted information attached to the quantum samples without destroying the phase that encodes the unknown value s. Oded Regev showed a method connecting DCP to a modular subset-sum problem, but the critical elimination step in his approach relied on an idealized mechanism called a subset-sum oracle. Simon proposes a procedure that groups many samples together and, through a combination of measurement and selection, eliminates the sample bits without using such an oracle.
After this processing, the resulting phase transfers one bit of the unknown value to a separate qubit. By repeating this recursively, the remaining bits can be recovered. The paper argues that at each stage enough quantum information survives, and that success probability can be boosted through a polynomial number of iterations. The central contribution is therefore a mathematical proof consisting of the algorithm and probability analysis—not a speedup observed on real hardware. No results from quantum circuit simulations or hardware experiments are reported.
There are also conditions for handling inputs containing errors. Simon claims the algorithm still works even when the proportion of "faulty samples"—those containing random classical information instead of the intended superposition—is as high as 1/O(log n), in the paper's notation. This is not a fixed error rate presented as a concrete figure; rather, it is a result deriving the order of the tolerable error rate under a defined input model, not one measured experimentally for robustness.
How Far the Implications Reach Lattice Problems
DCP draws cryptographers' attention not because attacks naturally spread from DCP to lattice problems, but because the direction runs the other way: existing reductions convert lattice problems into DCP. Regev's "Quantum Computation and Lattice Problems" (FOCS 2002, DOI: 10.1109/SFCS.2002.1181976) assumed an efficient solution to DCP and, on that basis, provided a quantum algorithm for the unique Shortest Vector Problem (unique-SVP).
Subsequently, Zvika Brakerski, Elena Kirshanova, Damien Stehlé, and Weiqiang Wen, in a PKC 2018 paper (DOI: 10.1007/978-3-319-76581-5_24), showed that LWE and eDCP are equivalent under quantum polynomial-time reductions. eDCP is a relaxed version of DCP, with the degree of relaxation depending on the noise rate of Learning With Errors (LWE). That paper summarizes Regev's result as "if DCP can be solved in quantum polynomial time, LWE can too," explicitly stating the direction from a DCP solution to LWE.
Simon explains that his new DCP algorithm can be combined with the reduction that Regev demonstrated and Brakerski et al. improved. Under that combination, he states that a √n polylog(n) approximation to the Shortest Vector Problem (SVP) in an n-dimensional lattice, and LWE instances denoted in the paper as α=√n polylog(n), can be solved in quantum polynomial time.
This claim is a logical consequence contingent on the DCP proof being correct and the premises of each reduction being satisfied. It is neither a study measuring a correlation nor an experiment demonstrating a causal effect in which solving DCP leads to breaking cryptography. Moreover, what is obtained is an approximate SVP solution, not a result that always finds the exact shortest vector. As for LWE, the result applies to a conditional range of parameters, and the paper does not claim to solve every LWE variant at once.
ML-KEM Has Not Been Broken Outright
ML-KEM, standardized by NIST in 2024 as FIPS 203 (DOI: 10.6028/NIST.FIPS.203), ties its security to the computational hardness of Module Learning With Errors (Module-LWE). The standard defines three parameter sets: ML-KEM-512, ML-KEM-768, and ML-KEM-1024. Simon's preprint, meanwhile, remains at the stage of demonstrating asymptotic implications for plain LWE and lattice problems; it has not been translated into a concrete attack breaking any specific ML-KEM parameter set that relies on Module-LWE.
The materials needed to judge practical relevance are also lacking. The paper provides no running time, number of required logical qubits, circuit depth, or error-correction cost for standard parameters. "Polynomial time" is a term classifying growth behavior as input size increases; it does not mean that a real-world cryptographic key can be broken quickly. No fixed quantum sample count is given either, making comparison with implementation benchmarks impossible.
Still, if the proof is verified, the theoretical shift would be significant, since the absence of a polynomial-time algorithm for DCP has long stood as an assumption underlying discussions of the quantum complexity of lattice problems. It is too early, though, to treat a freshly posted, single-author preprint as overturning established consensus. Changing cryptographic migration decisions will require expert scrutiny of the proof, independent re-derivation, and concrete resource estimates mapped onto standard parameters.