AWS Researcher Claims Polynomial-Time Solution to Quantum-Hard DCP, With Conditional Implications for Lattice Cryptography | XenoSpectrumコンテンツにスキップ<br>SEARCHESC<br>AI宇宙半導体量子コンピュータ

Enter で検索 · Esc で閉じる · ↑↓ で移動

Translated from the Japanese original<br>Read the Japanese original<br>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.

AD

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.

AD

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,...