Cyclotomic Cosets: Hidden Subgroup and Quantum Sieving Algorithm for Prime-Power Moduli

AI summary

Overview

Research area: Quantum algorithms for lattice and hidden-shift problems, with direct bearing on the security assumptions of post-quantum cryptography (Learning With Errors and its coset-state formulations).

Technical level: Advanced. The paper assumes familiarity with algebraic number theory (cyclotomic fields, ramification, field trace), finite group theory (nilpotent groups, lower central series), lattice cryptography, and the Kuperberg/Regev family of quantum sieving algorithms.

Scope (one sentence): The paper introduces a cyclotomic generalization of the Dihedral Coset Problem that retains an exact hidden-subgroup structure, and gives a quantum sieving algorithm that solves it — and, for a range of parameters, uniform EDCP and Gaussian S|LWE⟩ — in quasi-polynomial time for prime-power moduli q = p^t.

What This Paper Is About

LWE is the central hardness assumption of post-quantum cryptography, and Regev showed it connects to a quantum problem called the Dihedral Coset Problem (DCP), whose input states are exact coset states of order-two subgroups. Later work replaced DCP with the Extrapolated Dihedral Coset Problem (EDCP) to get an exact equivalence with LWE, but EDCP states generally lose the hidden-subgroup (coset) structure, which blocks the use of hidden-subgroup techniques.

This paper asks whether one can build a coset problem over cyclotomic rings — the Cyclotomic Coset Problem (CCP) — that keeps an exact hidden-subgroup structure for any prime power modulus q = p^t, not just powers of two, and whether the sieving approach that recently gave quasi-polynomial algorithms for power-of-two moduli can be carried over to that setting.

Key Contributions

1. Two new computational problems over cyclotomic rings. The authors define CyLWE (a cyclotomic analogue of LWE with a secret restricted to Z_q^n) and CCP (a p-ary analogue of DCP), and establish equivalences between these problems when p is constant.

2. A quantum Fourier transform over cyclotomic rings. They build a QFT over R_L = R/π^L R from the trace-dual pairing, which gives a rigorous definition of phase-state samples over such rings, in analogy with Kuperberg's phase states.

3. A sieving algorithm for CCP. The algorithm exploits the π-adic ideal chain R_q = R_L → R_{L-1} → … → R_1 = F_p, successively reducing phase states modulo π^L, π^{L-1}, …, π. For every fixed prime p and modulus q = p^t it solves CCP in time and sample complexity 2^{O_p(log n log q)} using polynomial quantum space.

4. Consequences for EDCP and S|LWE⟩. The sieve also applies to uniform EDCP and Gaussian S|LWE⟩, giving quasi-polynomial-time algorithms for all of these when q = poly(n), extending the power-of-two EDCP sieve of Bai et al. (CRYPTO 2025) to a cyclotomic setting.

Main Findings

• CCP is an exact hidden-subgroup problem. The ambient group is the semidirect product G_{n,q,p} = R_q^n ⋊ F_p with multiplication (x,j)(y,k) = (x + ζ_p^j y, j+k). For each secret s, the set H_s = {(λ_j s, j) : j ∈ F_p}, with λ_j = Σ_{i=0}^{j-1} ζ_p^i, is a subgroup of order p generated by (s,1), because λ_p = 1 + ζ_p + … + ζ_p^{p-1} = 0. CCP states are exactly left cosets of H_s.

• The cyclotomic group is nilpotent (Lemma 2). G_{n,q,p} is nilpotent of nilpotency class exactly t(p-1), with lower central series C^k(G) = π^{k-1} R_q^n ⋊ {0}; this follows from the ramification identity p = u_0 π^{p-1}, so q = u_0^t π^L with L = t(p-1).

• A π-adic chain of quotient rings. R_q ≅ R/π^L R, and |R_k| = p^k: multiplication by π^{k-1} identifies R/πR with π^{k-1}R/π^k R, so each successive quotient has p elements. This chain is what lets the sieve peel one level at a time.

• A trace-based duality (Lemma 4, Proposition 1). The map B_L(x,y) = Tr(xy/(p π^{L-1})) mod Z is a non-degenerate symmetric Z-bilinear form on R_L × R_L, which yields an isomorphism between R/π^L R and its character group, with characters χ_y(x) = exp(2iπ Tr(xy/(p π^{L-1}))).

• CCP specializes exactly to DCP at p = 2. For p = 2, ζ_2 = −1, λ_0 = 0, λ_1 = 1 and R_q = Z_q, so CCP is DCP, i.e., uniform EDCP with two branches.

• Reported complexity. The sieve solves CCP in time and sample complexity 2^{O_p(log n log q)} with polynomial quantum space, and gives quasi-polynomial time for uniform EDCP and Gaussian S|LWE⟩ when q = poly(n). Asymptotic notation is taken with respect to the lattice dimension n and security parameter κ; quasipolynomial means bounded by 2^{O(log^c n)} for some constant c ≥ 1.

• A stated limitation. The result does not by itself give a quasi-polynomial-time algorithm for standard LWE, because the currently known reduction produces only a limited number of approximate CCP states.

• Not a direct application of Imran–Ivanyos. The exact theorem of Imran and Ivanyos assumes access to a unitary U preparing the state and its inverse U^{-1}; here the input is only independent quantum samples, with neither the preparation circuit nor its inverse available. The authors therefore use their zero-sum algorithm and describe the state transformations explicitly, accounting for sample consumption and working space.

• Details not covered in the available text. The full statement of the sieving algorithm (Algorithm 1) and its step-by-step analysis are not included in the excerpt analyzed here; the QFT construction is presented up to Definition 8 in this text.

Methodology in Plain English

The authors design a new problem rather than attack an existing one directly. They replace the integers modulo q with a cyclotomic ring, where the prime p ramifies completely: p factors as π^{p-1} up to a unit. That single algebraic fact produces a nested chain of ideals from R_q down to F_p, and each step down the chain is very small — exactly p elements.

The quantum strategy mirrors Kuperberg-style sieving. Starting from coset states, a quantum Fourier transform converts them into phase states in which the secret appears only in a phase, tagged by a known label. The sieve then repeatedly combines phase states whose labels agree on a chosen level of the π-adic chain, producing new states whose labels are one level more divisible. Doing this steadily walks the states down the chain until enough information about the secret has been isolated. The authors explicitly track how many samples each combination consumes and how much quantum working memory is needed, since their access model is sample-based rather than gate-based.

The QFT itself is the technical workhorse: the standard Galois-ring Fourier transform does not directly cover this ramified ring (since Φ_p(X) ≡ (X−1)^{p-1} mod p), so they use the trace-dual pairing to define characters and build the transform from ordinary abelian Fourier transforms plus a change of coordinates.

Why This Matters

Impact on research. The paper widens the class of moduli for which quasi-polynomial quantum sieving algorithms are known for coset-type problems, from powers of two to cyclotomic prime powers, and it supplies a hidden-subgroup structure for a p-ary coset problem that previously had none outside p = 2. It also connects the algorithm to the nilpotent-group framework of Imran and Ivanyos while showing why that theorem does not apply verbatim.

Potential applications (each tied to a research direction, not a deployed product):

• Assessing the quantum security of LWE-based post-quantum cryptographic schemes across different modulus choices, including prime-power moduli.
• Informing parameter selection for lattice-based encryption and key-exchange schemes that use power-of-prime moduli.
• Providing algorithmic tools for hidden-shift and hidden-subgroup problems over number-theoretic rings beyond the dihedral case.
• Guiding cryptanalysis of ring-based constructions via the cyclotomic LWE formulation.

Industry relevance. Organizations standardizing or deploying lattice-based post-quantum cryptography need a clear picture of which parameter regimes are plausibly reachable by quantum sieving algorithms; this paper sharpens that picture for prime-power moduli, while explicitly stopping short of a claim against standard LWE.

Future Directions

• Close the sample-count gap. The authors state that LWE is not solved by their algorithm because the known reduction yields only a limited number of approximate CCP states; finding a reduction that produces enough CCP samples, or a sieve that works with fewer, is the central open problem.
• Handle non-constant p. The complexity 2^{O_p(log n log q)} hides a constant depending on p, and the nilpotency class t(p-1) need not be constant; extending the analysis to growing p is a natural next step.
• Broaden the modulus family. The paper extends the power-of-two results of Bai et al. (CRYPTO 2025) to cyclotomic prime powers; further generalizations to other moduli — a bottleneck also noted by Chailloux and Hermouet — remain open.
• Full resource accounting and circuit-level implementation. Since the access model here is sample-based rather than unitary-based, working out explicit state-preparation circuits, gate counts, and error tolerances for the QFT over R_L would make the complexity claims concrete.

Target Audience

Quantum algorithms researchers working on hidden-subgroup and hidden-shift problems; cryptographic researchers analyzing the quantum security of LWE and its coset-state formulations; mathematicians interested in quantum computation over ramified cyclotomic rings and nilpotent groups; and advanced graduate students who already know Kuperberg-style sieving and the basics of cyclotomic fields. Readers seeking an entry-level introduction to LWE or to quantum sieving will find the prerequisites steep.

Authors’ 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.