Paper 2026/2925

A Quasipolynomial Quantum Algorithm for the Vector Dihedral Coset Problem with Smooth Modulus

Aparna Gupte, MIT
Abstract

We give a quantum algorithm for the vector dihedral coset problem over $\mathbb{Z}_q^n$, in which the goal is to recover $\mathbf{s} \in \mathbb{Z}_q^n$ given independent samples of the form $\frac{1}{\sqrt{2}}\bigl(\ket{0,\mathbf{x}}+\ket{1,\mathbf{x}+\mathbf{s}}\bigr)$, for $\mathbf{x}\sim \mathbb{Z}_q^n$. When the modulus $q$ is $B$-smooth, the algorithm uses $n^{O(B^{1+o(1)}\log q)}B^{O(B^{2+o(1)}\log q)}$ samples and time. For $B = \mathrm{polylog}(n)$ and $q=\mathrm{poly}(n)$, this gives a quasipolynomial time- and sample-complexity. This extends the previously known quasipolynomial-time result for power-of-two moduli (Bonnetain, Naya-Plasencia, ASIACRYPT 2018; Bai, Jangir, Kirshanova, Ngo, Youmans, CRYPTO 2025). The algorithm proceeds by reducing the modulus one prime factor $p | q$ at a time. The key ingredient is a sieving procedure that clears the non-linear terms in the phase modulo $p$ via an algorithm of Ivanyos and Santha (TCS 2017) that finds non-zero $\mathbf{u} \in \mathbb{F}_p^\ell$ such that $\sum_{i \in [\ell]} u_i^d \mathbf{a}_i = 0 \mod p$ for degrees $1 \le d \le p-1$, given vectors $\mathbf{a}_1, \ldots, \mathbf{a}_\ell \in \mathbb{F}_p^n$ as input. The algorithm also applies to the extrapolated dihedral coset problem (EDCP) introduced by Brakerski, Kirshanova, Stehlé, and Wen (PKC 2018), which is known to be equivalent to LWE in the polynomial sample regime. However, our result does not yield a new attack on LWE in any regime, precisely because the known reduction from LWE to EDCP provides only polynomially many clean samples, whereas our algorithm requires quasipolynomially many samples. The main algorithm was obtained in a GPT-5.6 Sol conversation prompted by the author; the author is responsible for all statements, proofs, and correctness. Concurrent work of Boucher, Fouque, and Shen gives an algorithm with similar guarantees for prime-power moduli.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
Learning with ErrorsHidden Shift ProblemExtrapolated Dihedral Coset Problem
Contact author(s)
agupte @ mit edu
History
2026-11-21: last of 2 revisions
2026-11-17: received
See all versions
Short URL
https://ia.cr/2026/2925
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2026/2925,
      author = {Aparna Gupte},
      title = {A Quasipolynomial Quantum Algorithm for the Vector Dihedral Coset Problem with Smooth Modulus},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2925},
      year = {2026},
      url = {https://eprint.iacr.org/2026/2925}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.