Paper 2026/1591
A Polynomial-Time Quantum Algorithm for the Dihedral Coset Problem
Abstract
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. The algorithm can thus combine with Regev's reduction of lattice problems to DCP, improved by Brakerski, Kirshanova, Stehl{\'e} and Wen, to yield polynomial-time quantum algorithms for various lattice problems, such as finding a polynomial-factor approximation to the shortest vector in an $n$-dimensional lattice (SVP), and the ``learning with errors'' problem (LWE). The algorithm can tolerate a faulty sample rate as high as $1/O(\log{n})$, allowing the algorithm-reduction combination to efficiently solve, for example, SVP with a $\sqrt{n}$ polylog($n$) approximation factor, or LWE instances with $\alpha=\sqrt{n}$ polylog($n$).
BibTeX
@misc{cryptoeprint:2026/1591,
author = {Daniel R. Simon},
title = {A Polynomial-Time Quantum Algorithm for the Dihedral Coset Problem},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/1591},
year = {2026},
url = {https://eprint.iacr.org/2026/1591}
}