Established cryptographer claims polynomial-time quantum algorithm for the Dihedral Coset Problem

The approved preprint, if validated by other experts, could threaten lattice-based post-quantum standards

On 3 August 2026, a cryptographer published a preprint claiming a polynomial-time quantum algorithm for the Dihedral Coset Problem, a result that — if it withstands scrutiny — could shake the mathematical foundations of lattice-based post-quantum cryptography now being rolled out globally.

The paper, titled “A Polynomial-Time Quantum Algorithm for the Dihedral Coset Problem” was received by the IACR Cryptology ePrint Archive and approved on 6 August 2026.

Its author, Daniel R Simon — the same researcher behind the 1994 Simon’s algorithm that remains a cornerstone of quantum computing — proposes a technique that removes the need for an idealized “subset-sum oracle” —  a roadblock that has stymied progress on the problem since Oded Regev’s 2002 reduction linked DCP to hard lattice problems.

reduction linked DCP to hard lattice problems.

Simon’s approach groups quantum samples and processes them to erase unwanted information while preserving the phase encoding that carries the hidden solution. By applying this recursively, the procedure claims to recover the answer in polynomial time. When combined with established reductions, the paper argues this delivers polynomial-time quantum algorithms for approximate versions of the Shortest Vector Problem and certain Learning With Errors instances — the very hard problems that underpin NIST’s ML-KEM and ML-DSA post-quantum standards.

Despite the theoretical ambition, the preprint stops well short of demonstrating an attack on any deployed cryptographic system, offering no qubit counts, circuit-depth estimates, or concrete resource projections. Early commentary on community forums suggests the polynomial degree may be extremely large: one estimate for ML-KEM-512 parameters placed the required sample count around 2¹²⁸, roughly comparable to brute-forcing AES-128. One cryptography professional on LinkedIn noted that the attack presupposes quantum hardware that does not yet exist.

However, the paper itself frames the work as a preliminary draft, with the amplitude-analysis lemmas that carry the proof’s weight presented only as sketches rather than fully worked derivations. Verification remains the next critical step.

Simon has indicated he is in ongoing discussions with leading lattice-cryptography researchers. Independent specialists will need to confirm whether the erasure method functions under the stated assumptions, and whether the probability bounds hold throughout the recursive procedure.

The paper’s own authors label it preliminary, and the amplitude-analysis lemmas that bear the proof’s weight are given only as sketches.