Cyclotomic coset problem enables quantum sieve for prime power moduli
Cyclotomic Cosets: Hidden Subgroup and Quantum Sieving Algorithm for Prime-Power Moduli
Cryptography and Security
Summary
Understanding certain hard math problems helps protect data from hackers using future quantum computers. This paper introduces a new problem called the Cyclotomic Coset Problem, which has a special hidden structure that lets the authors design a quantum algorithm to solve it more efficiently. Their algorithm works especially well when the numbers involved are powers of a prime number. However, this advance does not immediately translate to solving the main cryptographic problem known as LWE, which secures many post-quantum cryptography systems.
What this means in practice
- •For quantum cryptographers: Design algorithms to test quantum hardness assumptions based on prime-power moduli and cyclotomic structures in lattice problems.
- •For quantum algorithm developers: Create quantum sieves exploiting cyclotomic coset structures to improve solving lattice-related problems with prime-power parameters.
A theory result. No direct application yet.
Authors
Mathias Boucher, Pierre-Alain Fouque, Yixin Shen
Abstract
The Learning With Errors (LWE) problem is a fundamental assumption in post-quantum cryptography. Regev established a quantum reduction from LWE to the Dihedral Coset Problem (DCP). Later, Brakerski et al. introduced the Extrapolated Dihedral Coset Problem (EDCP), proving its equivalence to LWE. However, unlike DCP, EDCP no longer admits a coset structure. This limits the direct application of techniques for hidden subgroup problems. In this work, we introduce the Cyclotomic Coset Problem (CCP), a cyclotomic generalization of DCP that preserves an exact hidden-subgroup structure. Let $ζ_p$ be a primitive $p$-th root of unity, let $π=ζ_p-1$, and write $q=p^t$ and $L=t(p-1)$. We work over $R_q=\mathbb Z_q[ζ_p] \cong \mathbb Z[ζ_p]/(π^L)$, where the isomorphism follows from the total ramification identity $(p)=(π)^{p-1}$. We exploit the resulting $π$-adic ideal chain to construct a quantum sieve that successively reduces phase states modulo $π^{L},π^{L-1},\ldots,π$. For every fixed prime $p$ and modulus $q=p^t$, our algorithm solves the CCP in time and sample complexity $2^{O_p(\log n\log q)}$, using polynomial quantum space. The sieve also applies to uniform EDCP and Gaussian S|LWE>, yielding quasi-polynomial time algorithms for all the above problems when $q=\text{poly}(n)$. This extends the power-of-two EDCP sieve of Bai et al. (CRYPTO 2025) to a cyclotomic setting. However, we emphasize that our result does not, by itself, yield a quasi-polynomial-time algorithm for standard LWE, because the currently known reduction produces only a limited number of approximate CCP states.