Cyclotomic Cosets: Hidden Subgroup and Quantum Sieving Algorithm for Prime-Power Moduli
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=pt and L=t(p−1). We work over Rq=ℤq[ζp] ≅ ℤ[ζ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,…,π. For every fixed prime p and modulus q=pt, our algorithm solves the CCP in time and sample complexity 2Op(log nlog 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=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.
Related
- Cyclotomic Structure and Exact Recurrences in Floquet Many-Body Quantum Dynamics
- Coset Lifted Product Codes: Constructing Quantum LDPC Codes from Non-Normal Subgroup Actions
- Projector Form of the Quantum Brachistochrone and Its Relation to Two-Boundary Quantum Algorithm Design
- Fast quantum algorithm for differential equations
- Scalable quantum-enhanced greedy algorithm for the maximum independent set problems on random regular graphs
BibTeX
@misc{boucher2026cyclotomic,
title = {{Cyclotomic Cosets: Hidden Subgroup and Quantum Sieving Algorithm for Prime-Power Moduli}},
author = {Mathias Boucher and Pierre-Alain Fouque and Yixin Shen},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.34996},
eprint = {2609.34996},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.34996},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Cyclotomic Cosets: Hidden Subgroup and Quantum Sieving Algorithm for Prime-Power Moduli
AU - Mathias Boucher
AU - Pierre-Alain Fouque
AU - Yixin Shen
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.34996
UR - https://arxiv.org/abs/2609.34996
AB - 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=ℤ_q[ζ_p] ≅ ℤ[ζ_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,…,π. For every fixed prime p and modulus q=p^t, our algorithm solves the CCP in time and sample complexity 2^O_p(log nlog 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=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.
ER -