⚛️ quantum physics

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

This paper introduces the Cyclotomic Coset Problem (CCP) as a hidden-subgroup-preserving generalization of the Dihedral Coset Problem and presents a quantum sieving algorithm that solves CCP, uniform EDCP, and Gaussian S|LWE> in quasi-polynomial time for prime-power moduli, though it does not yet yield a quasi-polynomial-time solution for standard LWE due to limitations in the reduction's state generation.

Original authors: Mathias Boucher, Pierre-Alain Fouque, Yixin Shen

Published 2026-09-29

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Mathias Boucher, Pierre-Alain Fouque, Yixin Shen

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the quiet, high-stakes world of digital security, a fundamental challenge has long been how to protect information from the future threat of quantum computers. For decades, cryptographers have relied on a mathematical puzzle known as Learning With Errors. Imagine trying to find a hidden path through a dense forest, but every time you take a step, the ground beneath you shifts slightly, throwing off your measurements. This "noise" makes the puzzle incredibly hard to solve for standard computers, yet it remains the bedrock of many proposed encryption systems designed to withstand quantum attacks. The security of these systems depends on the assumption that even a powerful quantum computer cannot efficiently reverse-engineer the hidden path from the noisy data.

To understand the strength of this assumption, researchers often translate the problem into a different language, one involving quantum states and hidden groups. Think of a quantum state as a delicate, invisible coin that can exist in a superposition of heads and tails simultaneously. In some versions of the problem, these coins are arranged in a way that reveals a hidden pattern, much like finding a specific rhythm in a complex song. For years, scientists have known how to solve a specific, simplified version of this pattern-finding task, but the more complex, realistic versions have remained stubbornly resistant to quantum solutions. The question has been whether a quantum computer could eventually crack the full, noisy version of the puzzle, or if the noise is strong enough to keep it safe forever.

A team of researchers from Rennes, France, has now taken a significant step toward answering this question by introducing a new mathematical framework that bridges the gap between the simple and the complex. They developed a method to solve a generalized version of the pattern-finding problem, which they call the Cyclotomic Coset Problem. This new approach works over a specific type of number system that behaves differently from the standard integers, allowing the researchers to apply a powerful technique known as quantum sieving. By carefully filtering and combining quantum states, their algorithm can peel away layers of complexity, gradually revealing the hidden secret. The result is a quantum algorithm that can solve this specific, generalized problem in a time that is significantly faster than exponential, though still slower than the lightning-fast speed of a polynomial-time solution.

However, the researchers are careful to clarify what their discovery does and does not mean for the future of encryption. While their method successfully solves the generalized problem for a wide range of parameters, it does not yet break the standard Learning With Errors problem used in real-world cryptography. The reason lies in the number of samples required. The algorithm needs a vast quantity of quantum data to function effectively, far more than what is currently available from the standard reduction that turns the encryption problem into the pattern-finding problem. In essence, the researchers have built a very powerful key, but the lock they are trying to open requires a key ring that is too large to be produced by current methods.

The core of their work involves a clever manipulation of quantum states over a structure called a cyclotomic ring. In simpler terms, they created a new way to organize the quantum information so that it retains a hidden structure, even when the original problem seemed to have lost it. They achieved this by defining a new type of group, a mathematical structure that allows them to use a "sieve" to filter out unwanted information. This sieve works by repeatedly combining quantum states in a way that cancels out noise and amplifies the signal of the hidden secret. The process is iterative, moving step by step through different levels of mathematical precision, much like refining a rough stone into a gem by removing small chips of material one layer at a time.

Their findings show that for a specific class of problems involving prime-power moduli, the hidden secret can be recovered in what is known as quasi-polynomial time. This is a middle ground between the slow, exponential time it takes for classical computers to solve hard problems and the instant speed of polynomial time. The algorithm uses a number of quantum samples that grows slowly enough to be considered efficient for certain parameters, but the researchers emphasize that this efficiency does not automatically translate to a break in standard encryption. The reduction from the standard encryption problem to their new problem only produces a limited number of the necessary quantum states, creating a bottleneck that prevents the algorithm from being applied directly to break current cryptographic systems.

The paper also explores the relationship between their new problem and other known quantum challenges, such as the Dihedral Coset Problem and the Extrapolated Dihedral Coset Problem. They demonstrate that their method can solve these related problems when the modulus is a power of a prime number, extending previous results that were limited to powers of two. This generalization is significant because it shows that the underlying mathematical structure is more robust and versatile than previously thought. By proving that these problems are equivalent under certain conditions, the researchers provide a clearer map of the landscape of quantum-resistant cryptography, showing where the weak points might be and where the defenses remain solid.

Ultimately, this work serves as a rigorous stress test for the assumptions underlying post-quantum cryptography. It confirms that while quantum computers possess the theoretical power to solve certain complex pattern-finding problems much faster than classical machines, the specific noise and constraints of the Learning With Errors problem provide a formidable barrier. The researchers have shown that even with advanced quantum techniques, the path to breaking the encryption is not as direct as one might hope. The "noise" in the system is not just a minor inconvenience; it is a fundamental feature that, when combined with the limitations of current quantum sample generation, keeps the hidden path secure. The study concludes that while the field has advanced significantly in understanding the mechanics of these quantum puzzles, the standard encryption methods remain safe from this particular line of attack, at least for the foreseeable future.

Technical Summary: Cyclotomic Cosets, Hidden Subgroup, and Quantum Sieving for Prime-Power Moduli

1. Problem Context and Motivation

The Learning With Errors (LWE) problem is a foundational assumption in post-quantum cryptography. While Regev established a quantum reduction from LWE to the Dihedral Coset Problem (DCP), and Brakerski et al. later introduced the Extrapolated Dihedral Coset Problem (EDCP) to prove equivalence with LWE, a significant structural limitation exists. Unlike DCP, general EDCP states do not possess an exact hidden-subgroup structure because the set of translations does not form a subgroup. This limitation prevents the direct application of efficient hidden-subgroup techniques, particularly for moduli that are not powers of two.

Recent work by Bai et al. (CRYPTO 2025) achieved a quasi-polynomial-time quantum algorithm for EDCP and Gaussian $S|LWE\rangle$ over power-of-two moduli ( $q=2^t$ ) by exploiting a specific 2-adic ideal chain. However, generalizing this to arbitrary prime-power moduli ( $q=p^t$ ) has proven difficult because the dihedral group of order $2q$ is nilpotent only if $q$ is a power of two. Consequently, standard nilpotent group sieving techniques (such as those by Imran and Ivanyos) could not be directly applied to EDCP or DCP with non-power-of-two moduli.

2. Methodology and Core Construction

2.1 The Cyclotomic Coset Problem (CCP)

To overcome the lack of a hidden-subgroup structure in EDCP for general prime powers, the authors introduce the Cyclotomic Coset Problem (CCP). This problem is defined over the cyclotomic ring $R_q = \mathbb{Z}_q[\zeta_p]$ , where $p$ is a prime, $q=p^t$ , and $\zeta_p$ is a primitive $p$ -th root of unity.

The authors define a semidirect product group $G_{n,q,p} = R_q^n \rtimes \mathbb{F}_p$ . They prove that this group is nilpotent with a nilpotency class of $t(p-1)$ . Within this group, they identify a hidden subgroup $H_s$ generated by $(s, 1)$ , where $s$ is the secret vector. The coset states associated with this subgroup take the form:
$|\phi_{x,s}\rangle = \frac{1}{\sqrt{p}} \sum_{j \in \mathbb{F}_p} |j\rangle |x + \lambda_j s \rangle$
where $\lambda_j = \sum_{i=0}^{j-1} \zeta_p^i$ . When $p=2$ , this construction reduces exactly to the standard DCP.

2.2 Quantum Fourier Transform (QFT) over Cyclotomic Rings

A critical technical component is the definition and efficient implementation of the Quantum Fourier Transform over the ring $R_L = R/\pi^L R$ , where $\pi = \zeta_p - 1$ . Using the field trace and the $\pi$ -adic decomposition of the ideal $(p) = (\pi)^{p-1}$ , the authors construct a QFT that maps CCP samples to phase states.

This transformation converts the problem of recovering $s$ from coset states into the Phase-State Problem (PSP), where the secret is encoded in the phase of the quantum state:
$|\psi_y\rangle = \frac{1}{\sqrt{p}} \sum_{j \in \mathbb{F}_p} \chi_y(\lambda_j s) |j\rangle$
Here, $\chi_y$ is a character of the additive group of the ring.

2.3 The Quantum Sieving Algorithm

The authors adapt the "Simon-meets-Kuperberg" framework to the cyclotomic setting. The algorithm operates by iteratively reducing the modulus level using the $\pi$ -adic ideal chain:
$R_q \cong R_{\pi^L} \to R_{\pi^{L-1}} \to \dots \to R_{\pi} \cong \mathbb{F}_p$

The sieving process involves:

Zero-Sum Search: Given a set of phase-state samples with labels $y_i$ , the algorithm finds a subsequence such that $\sum y_i \equiv 0 \pmod \pi$ . This is achieved using a deterministic zero-sum search algorithm (based on Imran and Ivanyos) applied to the residues modulo $\pi$ .
State Combination: By tensoring the corresponding quantum states and performing specific basis changes and measurements, the algorithm produces a new phase-state sample with a label in the lower ring $R_{\pi^{L-1}}$ .
Iteration: This process is repeated $L-1$ times to reduce the problem to the base case over $\mathbb{F}_p$ , where the secret can be recovered via linear algebra.
Lifting: Once $s \pmod p$ is found, the algorithm recursively solves for the higher powers of $p$ to recover the full secret $s \in \mathbb{Z}_q^n$ .

3. Key Contributions

Introduction of CCP and CyLWE: The paper defines the Cyclotomic Coset Problem (CCP) and Cyclotomic LWE (CyLWE). It establishes that for constant $p$ , these problems are equivalent to their classical counterparts (DCP and LWE) and possess a hidden-subgroup structure over a nilpotent group, unlike general EDCP.
Cyclotomic QFT and Phase States: The authors rigorously define the QFT over cyclotomic rings $R_q$ and demonstrate how to transform CCP samples into phase states, enabling the application of sieving techniques.
Quasi-Polynomial Sieving Algorithm: They present a quantum algorithm (Algorithm 1) that solves CCP in quasi-polynomial time ( $2^{O(\log n \log q)}$ ) using polynomial quantum space, provided the number of samples is also quasi-polynomial.
Generalization of Previous Results: The work extends the quasi-polynomial-time results of Bai et al. (which were limited to $q=2^t$ ) to any prime-power modulus $q=p^t$ .
Equivalence Proofs: The paper provides quantum reductions showing that:
- Uniform EDCP and Gaussian $S|LWE\rangle$ over prime-power moduli can be reduced to CCP.
- Consequently, quasi-polynomial-time quantum algorithms exist for uniform EDCP and Gaussian $S|LWE\rangle$ when $q=p^t$ .

4. Results and Complexity

Complexity: The proposed algorithm solves CCP with a time and sample complexity of $2^{O(\log n \log q)}$ using polynomial quantum space.
Scope: The results apply to any modulus $q = p^t$ where $p$ is a fixed prime.
Reductions: The paper establishes that solving CCP allows for solving uniform EDCP and Gaussian $S|LWE\rangle$ in quasi-polynomial time under the same parameter constraints.

5. Significance and Limitations

The authors emphasize that while this work significantly advances the understanding of quantum algorithms for lattice-based problems over prime-power moduli, it does not yield a quasi-polynomial-time algorithm for standard LWE.

The limitation arises from the reduction chain:

Standard LWE reduces to DCP (or EDCP).
DCP/EDCP reduces to CCP.
The CCP solver requires a quasi-polynomial number of samples.

The known reductions from LWE to DCP/EDCP produce only a limited (polynomial) number of approximate states. Since the number of samples required by the CCP solver exceeds the number of samples available from the LWE reduction, the overall complexity for solving standard LWE remains exponential.

Thus, the paper's primary contribution is theoretical: it extends the power of nilpotent group sieving to a broader class of moduli and provides a unified framework for coset problems over cyclotomic rings, while maintaining a modest stance on the immediate threat to standard LWE security.