A Polynomial-Time Quantum Algorithm for the Dihedral Coset Problem

What a lovely hat

Is it made out of tin foil?

Paper 2026/1591

A Polynomial-Time Quantum Algorithm for the Dihedral Coset Problem

Daniel R. Simon, Amazon Web Services

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$).

Metadata

Available format(s)

PDF

Category<br>Attacks and cryptanalysis

Publication info<br>Preprint.

Keywords<br>quantumpost-quantumlattices

Contact author(s)

dcp-paper @ amazon com

History

2026-08-06: approved

2026-08-03: received

See all versions

Short URL<br>https://ia.cr/2026/1591<br>License

CC BY

BibTeX<br>Copy to clipboard

@misc{cryptoeprint:2026/1591,<br>author = {Daniel R. Simon},<br>title = {A Polynomial-Time Quantum Algorithm for the Dihedral Coset Problem},<br>howpublished = {Cryptology {ePrint} Archive, Paper 2026/1591},<br>year = {2026},<br>url = {https://eprint.iacr.org/2026/1591}

Note: In order to protect the privacy of readers, eprint.iacr.org<br>does not use cookies or embedded third party content.