Source-linked AI summary
Cyclotomic Cosets: Hidden Subgroup and Quantum Sieving Algorithm for Prime-Power Moduli
Mathias Boucher, Pierre-Alain Fouque, Yixin Shen
TL;DR
General EDCP does not retain DCP’s exact hidden-subgroup structure, motivating a cyclotomic coset problem. The paper introduces CCP and a cyclotomic Fourier-transform approach to phase states, then applies a sieve to related problems; the authors note that this does not by itself yield a quasi-polynomial-time algorithm for standard LWE.
Problem
General EDCP states do not retain DCP’s exact hidden-subgroup structure, motivating a coset problem related to EDCP and DCP.
Source: §1 · pp. 2–3Method
The paper introduces CCP and defines cyclotomic phase-state samples using a quantum Fourier transform over cyclotomic rings.
Source: §1.1 · p. 4, §3 · p. 11Results
The paper concludes that its algorithm yields quasi-polynomial time for related problems when q is a power of a fixed prime.
Source: §6 · p. 22Takeaways & Limitations
A sample of CyLWE can be converted into p −1 samples of LWE.
Source: §5.1 · p. 20The sieve requires more CCP samples than the known reduction from LWE to DCP supplies, so it does not by itself give a quasi-polynomial-time algorithm for standard LWE.
Source: §6.2 · p. 25
Abstract
from arXiv · showhide
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 $\zeta_p$ be a primitive $p$-th root of unity, let $\pi=\zeta_p-1$, and write $q=p^t$ and $L=t(p-1)$. We work over $R_q=\mathbb Z_q[\zeta_p] \cong \mathbb Z[\zeta_p]/(\pi^L)$, where the isomorphism follows from the total ramification identity $(p)=(\pi)^{p-1}$. We exploit the resulting $\pi$-adic ideal chain to construct a quantum sieve that successively reduces phase states modulo $\pi^{L},\pi^{L-1},\ldots,\pi$. 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.
1 Introduction
EDCP variants are linked to LWE, but general EDCP lacks DCP’s exact hidden-subgroup structure; this motivates a cyclotomic coset problem. The paper introduces CCP and related tools, then applies its sieve to uniform EDCP and S|LWE> in a broader prime-power setting.
1 Introduction
- LWE is a central post-quantum cryptographic problem, and DCP provides a coset-state formulation connected to lattice problems.DCP asks to recover a secret from states that are exact coset states of order-two subgroups of a generalized dihedral group.Source: §1 · pp. 1–2
- General EDCP states lack DCP’s exact hidden-subgroup structure, while earlier EDCP sieving results covered power-of-two moduli.This motivates a new coset problem related to EDCP and DCP for prime-power q.Source: §1 · pp. 2–3
- The algorithm is analyzed for independent quantum samples without access to the state-preparation circuit or its inverse.The authors use the zero-sum algorithm and describe transformations with sample consumption and working space accounted for.Source: §1 · p. 4
1.1 Cyclotomic Coset
- CCP is a cyclotomic generalization of DCP defined by recovering a secret from independent states formed from cosets of a subgroup.The associated group is nilpotent, and its hidden-subgroup problem is close to a generalized hidden-shift problem.Source: §1.1 · p. 4
1.2 Organization and contributions
- The paper introduces CyLWE and CCP as cyclotomic analogues of LWE and DCP, respectively, and establishes equivalences when p is constant..Source: §1.2 · p. 5
- A quantum Fourier transform over cyclotomic rings defines phase-state samples that serve as input to the paper’s sieving algorithm.The sieve is presented as an instance of the framework of Imran and Ivanyos [10].Source: §1.2 · p. 5
- For a certain parameter range, the sieve solves uniform EDCP and S|LWE> in quasi-polynomial time, generalizing the power-of-two results of.The stated application covers q that is a power of a fixed prime.Source: §1.2 · p. 5
2 Preliminaries
The preliminaries establish the cyclotomic-ring and group structures, define the paper’s computational problems, and recall the quantum Fourier transform. They also provide the notation and lattice background used in those definitions.
2.2 Lattices and cyclotomic lattices
- The paper defines Gaussian weights through a coefficient embedding and states that the Gaussian on the coefficient lattice factors into independent one-dimensional discrete Gaussians.The factorization is stated for the coefficient lattice, not arbitrary lattices.Source: §2.2 · p. 7
2.3 The cyclotomic group
- The cyclotomic group G_n,q,p is nilpotent with nilpotency class t(p − 1), as its lower central series is described using successive powers of π.The paper’s argument identifies C_k(G) with π^(k−1)R_q^n for k ≥ 2.Source: §2.3 · p. 8
2.4 Computational problems
- The preliminaries define search LWE and CyLWE, with CyLWE using a rational secret and a coefficient error distribution rather than the usual Ring-LWE setting.For fixed p, the ring degree is p − 1 and n is an independent vector dimension.Source: §2.4 · pp. 8–9
- The HSP and coset-problem definitions formalize recovering hidden subgroups from coset samples, including the dihedral problem over Z_q^n.The DCP samples use independent uniform elements of Z_q^n.Source: §2.4 · pp. 9–10
- CCP asks to recover a secret s from independent quantum samples whose branches use offsets λ_j s and uniform elements of R_q^n.The secret is embedded coordinatewise as a constant in the cyclotomic ring; for p = 2, CCP is DCP.Source: §2.4 · p. 10
2.5 Quantum Fourier Transform
- The QFT over Z_N has an approximation with operator-norm error at most ε using poly(log N, log(1/ε)) elementary gates.For N a power of a fixed prime, its ideal radix expansion uses O(log^2 N) constant-dimensional Fourier and controlled-phase gates.Source: §2.5 · pp. 10–11
3 Quantum Fourier Transform over cyclotomic rings
This section constructs a Fourier transform over cyclotomic quotients using trace-dual characters, then uses it to turn CCP samples into phase states. Those states provide the input to the later sieving procedure.
3.1 The duality in RL
- Trace pairing identifies the additive dual of the cyclotomic quotient with elements of the quotient itself, giving characters with useful algebraic properties.The character family is indexed by elements of R_L.Source: §3.1 · pp. 11–12
3.2 Construction of the Quantum Fourier Transform
- For fixed p and L = t(p −1), the quantum Fourier transform over R_L has an implementation with time polynomial in t and log(1/ε).The transform uses the trace-dual pairing, implemented through ordinary abelian Fourier transforms and a change of coordinates.Source: §3.2 · pp. 13–14
3.3 Phase-state Problem
- Applying the cyclotomic QFT to a CCP sample produces phase states in which the secret is encoded in the phase.Measuring the label register yields independent uniform labels, and the factor depending on the original sample is only a global phase.Source: §3.3 · pp. 14–15
- For q = p^t and L = t(p −1), CCP reduces to recovering the secret from phase-state samples.The phase states are obtained by applying the QFT to the CCP sample's second register.Source: §3.3 · p. 15
4 A practical algorithm for solving the CCP
The section gives a sample-based CCP solver by reducing phase states through successive levels of the cyclotomic ideal chain. For fixed p, it achieves time 2^O(log n log q) with polynomial quantum space.
4 A practical algorithm for solving the CCP
- The authors present their CCP algorithm as a cyclotomic reformulation of Imran and Ivanyos's framework, with explicit time and space analysis.The exact theorem does not directly fit the setting, which supplies independent samples rather than a state-preparation unitary and its inverse.Source: §4 · p. 16
4.1 Solver for the easy instance of PSPn,1,p
- At the base level R_1 ≅ F_p, measuring a phase state in the Fourier basis recovers ⟨y, s⟩, and n linearly independent labels recover s mod p.The labels are linearly independent with constant probability.Source: §4.1 · p. 17
4.2 Sieving step
- At each sieve step, a zero-sum selection of labels modulo π lets the algorithm combine phase states into a sample one level lower.The output label is uniform when the zero-sum subsequence is selected using only the residues modulo π.Source: §4.2 · pp. 17–18
4.3 Description of the sieving algorithm
- For fixed p, the CCP algorithm uses 2^O(log n log q) time and polynomial quantum space, with sample complexity 2^Ω(log n log q).The algorithm succeeds with constant probability.Source: §4.3 · pp. 18–19
- The full sieve groups samples into zero-sum sequences, descends from PSP_n,L,p to PSP_n,1,p, recovers the secret modulo p, and repeats to recover the full secret.The list of samples shrinks across levels; O(n) final-level phase states suffice to recover s mod p.Source: §4.3 · pp. 18–19
5 Equivalences between classical and cyclotomic problems
The section relates classical lattice and dihedral problems to their cyclotomic counterparts through sample conversions. It also discusses why a direct CyLWE-to-CCP reduction remains prospective.
5.1 Between LWE and CyLWE
- With constant p, LWE and CyLWE samples can be converted in both directions while preserving the secret, with p −1 samples used in the conversion to LWE.The stated sample conversion establishes the connection between search LWE and cyclotomic LWE.Source: §5.1 · p. 20
5.2 Between DCP and CCP
- DCP and CCP samples convert in both directions with the same secret, with success probabilities p/2p−1 and 2/p, respectively.Source: §5.2 · p. 21
5.3 A potential direct reduction from CyLWE to CCP?
- A direct CyLWE-to-CCP reduction is proposed as a possibility, but it requires results on random q-ary lattice topology that the authors do not claim.The authors state that this route would improve only slightly on the indirect reduction through LWE and DCP.Source: §5.3 · p. 22
6 Impact and discussions
This section extends the CCP-based sieve to uniform EDCP and Gaussian S|LWE over prime-power moduli. It also notes that sample limits in the known LWE-to-DCP reduction prevent this result alone from yielding quasi-polynomial standard-LWE.
6.1 On the Extrapolated Dihedral Coset Problem.
- The algorithm solves U-EDCP for any prime-power modulus q in time 2^O(log n log q).Source: §6.1 · p. 23
6.2 An algorithm for Gaussian S|LWE
- A constant number of U-EDCP samples can be converted into PSP samples involving the same secret, enabling the Gaussian S|LWE procedure.Source: §6.2 · pp. 23–24
- The result also gives an alternative quasi-polynomial algorithm for uniform EDCP without reducing it to DCP.Source: §6.2 · p. 25
- For q = poly(κ), q = p^t with fixed prime p, and the stated r conditions, the Gaussian S|LWE solver runs in time 2^O(log^2 n).Source: §6.2 · p. 25
- The Gaussian S|LWE algorithm relies on defining a quantum Fourier transform on Rq and explicitly specifying phase-state samples.Source: §6.2 · p. 25
- The sieve requires more CCP samples than the known LWE-to-DCP reduction supplies, so this result alone does not yield quasi-polynomial standard-LWE.Source: §6.2 · p. 25