arXiv:2609.34996
Cyclotomic Cosets: Hidden Subgroup and Quantum Sieving Algorithm for Prime-Power Moduli
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.
AI Summary
The paper asks whether quantum coset sieving can be extended from power-of-two moduli to powers of any fixed prime while retaining an exact hidden-subgroup structure. It introduces the Cyclotomic Coset Problem (CCP) over $R_q=\mathbb Z_q[\zeta_p]$, where $q=p^t$, using order-$p$ subgroups of $R_q^n\rtimes\mathbb F_p$. For $p=2$, CCP is DCP; the formal CCP definition restricts the secret to $\mathbb Z_q^n$. The construction uses total ramification, $(p)=(\zeta_p-1)^{p-1}$, to obtain an ideal chain of length $L=t(p-1)$. A trace-dual Fourier transform converts coset samples into phase states. A zero-sum algorithm from prior work selects labels summing to zero modulo $\pi=\zeta_p-1$; combining their states lowers the level from $R/\pi^L$ to $R/\pi^{L-1}$. Iterating yields linear equations over $\mathbb F_p$, followed by digit-by-digit secret recovery. For fixed $p$, the stated time and sample complexity is $2^{O_p(\log n\log q)}$, with polynomial quantum space, hence quasi-polynomial time when $q=\operatorname{poly}(n)$. Sample conversions connect CCP to DCP and uniform EDCP. The paper also claims an extension to Gaussian $S|\mathrm{LWE}\rangle$ under width conditions $r=\Omega(\sqrt\kappa)$ and $q/r=\Omega(\sqrt\kappa)$. The sieve is presented as a sample-based specialization of an existing nilpotent-group framework, rather than a new general algorithm. Its quasi-polynomial sample requirement exceeds what known LWE reductions supply as sufficiently accurate coset states, so it does not yield a quasi-polynomial algorithm for standard LWE. A direct cyclotomic-LWE-to-CCP reduction remains unproved.
Error found: The Gaussian application invokes a conversion lemma stated only for branch length M=q on inputs with M=cr, although the construction extends directly to general M≥2 and repairs this local mismatch. The body’s unrestricted-prime complexity statements omit essential p dependence and are justified only with the abstract’s fixed-prime restriction. The CCP sample-complexity proof contains invalid inequality manipulations, although exact bucket counting recovers the advertised fixed-prime bound.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.