Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.34996

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

Mathias Boucher, Pierre-Alain Fouque, Yixin Shen

quant-phcs.CRSubmitted Sep 28, 2026• Announced Sep 29, 2026• 1 citation
arXivHTMLPDF

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.

Little sign of AI-generated textPossible errorOverclaimsUnclear writing

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.

Related papers

A reduction from LWE problem to dihedral coset problem

Fada Li, Wan‐Su Bao, Xiang-Qun Fu +2 more

Learning with Errors (LWE) problems are the foundations for numerous applications in lattice-based cryptography and are provably as hard as approximate lattice problems in the worst case. Here we present a reduction from LWE problem to dihedral coset problem(DCP). We present a quantum algorithm to generate the input of the two point problem which hides the solution of LWE. We then give a new reduction from two point problem to dihedral coset problem on D_{{({n^{13})}^{n\log n}}}. Our reduction implicate that any algorithm solves DCP in subexponential time would lead a quantum algorithm for LWE.

arXiv:1305.3769•May 16, 2013•2 citations

Beyond LWE: Post-Quantum Assumptions under a Counterfactual Break of the Dihedral Coset Problem

Ramses Fernandez

A refuted 2026 claim of an efficient quantum algorithm for the Dihedral Coset Problem (DCP) motivates this survey of the consequences of a genuine breakthrough. We distinguish a noiseless cyclic coset-state solver, a solver with a prescribed failure exponent, and an extrapolated-state solver. Regev's rare-corruption observation already makes the first hypothesis sufficient for lattice algorithms at some polynomial approximation factors; the witnessing algorithm determines the quantitative bounds. We compose unstructured reductions with explicit sample, state-preparation and success conditions, and compare their sufficient guarantees with more than thirty lattice and non-lattice assumptions. We restate the structured state conversion of Wen and Zheng and audit its forward parameter certificate; the printed bound supplies no certificate at the ML-KEM ring and modulus. We use an explicit affine embedding for heuristic gap estimates, explain the lossiness connection from decision NTRU to search Ring-LWE, and distinguish ordinary from module uniqueness. Chen's withdrawn 2024 quantum algorithm for LWE and a proposed repair of its post-processing would, if correct, reach only a many-sample, small-noise LWE regime that the failure-exponent hypothesis already covers for exponents below $1/2$, and no deployed parameter set. Tables separate rigorous consequences, heuristic comparisons and unverified applications, and distinguish solving a proof assumption from attacking a scheme. Classical structural attacks on Classic McEliece, which do not involve DCP but put the concrete security of the scheme under revision, are summarised here and analysed in detail in a companion paper. The survey closes with open questions and a scenario-planning checklist that requires a complete efficient reduction.

arXiv:2610.36731•Oct 27, 2026•0 citations

The dihedral hidden subgroup problem

Imin Chen, David I. Sun

Abstract The hidden subgroup problem (HSP) is a cornerstone problem in quantum computing, which captures many problems of interest and provides a standard framework algorithm for their study based on Fourier sampling, one class of techniques known to provide quantum advantage, and which succeeds for some groups but not others. The quantum hardness of the HSP problem for the dihedral group is a critical question for post-quantum cryptosystems based on learning with errors and also appears in subexponential algorithms for constructing isogenies between elliptic curves over a finite field. In this article, we give an updated overview of the dihedral hidden subgroup problem as approached by the “standard” quantum algorithm for HSP on finite groups, detailing the obstructions for strong Fourier sampling to succeed and summarizing other known approaches and results. In our treatment, we “contrast and compare” as much as possible the cyclic and dihedral cases, with a view to determining bounds for the success probability of a quantum algorithm that uses m m coset samples to solve the HSP on these groups. In the last sections, we prove a number of no-go results for the dihedral coset problem (DCP), motivated by a connection between DCP and cloning of quantum states. The proofs of these no-go results are then adapted to give nontrivial upper bounds on the success probability of a quantum algorithm that uses m m coset samples to solve DCP.

arXiv:2106.09907•Journal of Mathematical Cryptology•Jan 1, 2024•4 citations

Quantum Algorithms for Variants of Average-Case Lattice Problems via Filtering

Yuehua Chen, Qipeng Liu, Mark Zhandry

We show polynomial-time quantum algorithms for the following problems: (*) Short integer solution (SIS) problem under the infinity norm, where the public matrix is very wide, the modulus is a polynomially large prime, and the bound of infinity norm is set to be half of the modulus minus a constant. (*) Learning with errors (LWE) problem given LWE-like quantum states with polynomially large moduli and certain error distributions, including bounded uniform distributions and Laplace distributions. (*) Extrapolated dihedral coset problem (EDCP) with certain parameters. The SIS, LWE, and EDCP problems in their standard forms are as hard as solving lattice problems in the worst case. However, the variants that we can solve are not in the parameter regimes known to be as hard as solving worst-case lattice problems. Still, no classical or quantum polynomial-time algorithms were known for the variants of SIS and LWE we consider. For EDCP, our quantum algorithm slightly extends the result of Ivanyos et al. (2018). Our algorithms for variants of SIS and EDCP use the existing quantum reductions from those problems to LWE, or more precisely, to the problem of solving LWE given LWE-like quantum states. Our main contribution is solving LWE given LWE-like quantum states with interesting parameters using a filtering technique.

arXiv:2108.11015•Aug 25, 2021•10 citations

A subexponential-time quantum algorithm for LWE problem

Fada Li, Wan‐Su Bao, Xiang-Qun Fu +2 more

Learning with Errors (LWE) problems are the foundations for numerous applications in lattice-based cryptography and are provably as hard as approximate lattice problems in the worst case. Here we present a reduction from LWE problem to dihedral coset problem(DCP). We present a quantum algorithm to generate the input of the two point problem which hides the solution of LWE. We then give a new reduction from two point problem to dihedral coset problem on D_{{({n^{13})}^{n\log n}}}. Our reduction implicate that any algorithm solves DCP in subexponential time would lead a quantum algorithm for LWE.

•May 16, 2013•0 citations

On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism

Cristopher Moore, Alexander C. Russell, Piotr Śniady

It is known that any quantum algorithm for graph isomorphism that works within the framework of the hidden subgroup problem (HSP) must perform highly entangled measurements across $\Omega(n\log n)$ coset states. One of the only known models for how such a measurement could be carried out efficiently is Kuperberg's algorithm for the HSP in the dihedral group, in which quantum states are adaptively combined and measured according to the decomposition of tensor products into irreducible representations. This “quantum sieve” starts with coset states and works its way down toward representations whose probabilities differ depending on, for example, whether the hidden subgroup is trivial or nontrivial. In this paper we show that no such approach can produce a polynomial-time quantum algorithm for graph isomorphism. Specifically, we consider the natural reduction of graph isomorphism to the HSP over the wreath product $S_n\wr\mathbb{Z}_2$. Using a recently proved bound on the irreducible characters of $S_n$, we show that no algorithm in this family can solve graph isomorphism in less than $\mathrm{e}^{\Omega(\sqrt{n})}$ time, no matter what adaptive rule it uses to select and combine quantum states. In particular, algorithms of this type can offer essentially no improvement over the best known classical algorithms, which run in time $\mathrm{e}^{O(\sqrt{n\log n})}$.

arXiv:quant-ph/0609138•SIAM Journal on Computing•Jan 1, 2010•16 citations
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ζ_pζp​ be a primitive ppp-th root of unity, let π=ζp−1π=ζ_p-1π=ζp​−1, and write q=ptq=p^tq=pt and L=t(p−1)L=t(p-1)L=t(p−1). We work over Rq=Zq[ζp]≅Z[ζp]/(πL)R_q=\mathbb Z_q[ζ_p] \cong \mathbb Z[ζ_p]/(π^L)Rq​=Zq​[ζp​]≅Z[ζp​]/(πL), where the isomorphism follows from the total ramification identity (p)=(π)p−1(p)=(π)^{p-1}(p)=(π)p−1. We exploit the resulting πππ-adic ideal chain to construct a quantum sieve that successively reduces phase states modulo πL,πL−1,…,ππ^{L},π^{L-1},\ldots,ππL,πL−1,…,π. For every fixed prime ppp and modulus q=ptq=p^tq=pt, our algorithm solves the CCP in time and sample complexity 2Op(log⁡nlog⁡q)2^{O_p(\log n\log q)}2Op​(lognlogq), 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)q=\text{poly}(n)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.
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 Rq=Zq[ζp]R_q=\mathbb Z_q[\zeta_p]Rq​=Zq​[ζp​], where q=ptq=p^tq=pt, using order-ppp subgroups of Rqn⋊FpR_q^n\rtimes\mathbb F_pRqn​⋊Fp​. For p=2p=2p=2, CCP is DCP; the formal CCP definition restricts the secret to Zqn\mathbb Z_q^nZqn​.
The construction uses total ramification, (p)=(ζp−1)p−1(p)=(\zeta_p-1)^{p-1}(p)=(ζp​−1)p−1, to obtain an ideal chain of length L=t(p−1)L=t(p-1)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 π=ζp−1\pi=\zeta_p-1π=ζp​−1; combining their states lowers the level from R/πLR/\pi^LR/πL to R/πL−1R/\pi^{L-1}R/πL−1. Iterating yields linear equations over Fp\mathbb F_pFp​, followed by digit-by-digit secret recovery. For fixed ppp, the stated time and sample complexity is 2Op(log⁡nlog⁡q)2^{O_p(\log n\log q)}2Op​(lognlogq), with polynomial quantum space, hence quasi-polynomial time when q=poly⁡(n)q=\operatorname{poly}(n)q=poly(n).
Sample conversions connect CCP to DCP and uniform EDCP. The paper also claims an extension to Gaussian S∣LWE⟩S|\mathrm{LWE}\rangleS∣LWE⟩ under width conditions r=Ω(κ)r=\Omega(\sqrt\kappa)r=Ω(κ​) and q/r=Ω(κ)q/r=\Omega(\sqrt\kappa)q/r=Ω(κ​). 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.
Learning with Errors (LWE) problems are the foundations for numerous applications in lattice-based cryptography and are provably as hard as approximate lattice problems in the worst case. Here we present a reduction from LWE problem to dihedral coset problem(DCP). We present a quantum algorithm to generate the input of the two point problem which hides the solution of LWE. We then give a new reduction from two point problem to dihedral coset problem on D_{{({n^{13})}^{n\log n}}}. Our reduction implicate that any algorithm solves DCP in subexponential time would lead a quantum algorithm for LWE.
A refuted 2026 claim of an efficient quantum algorithm for the Dihedral Coset Problem (DCP) motivates this survey of the consequences of a genuine breakthrough. We distinguish a noiseless cyclic coset-state solver, a solver with a prescribed failure exponent, and an extrapolated-state solver. Regev's rare-corruption observation already makes the first hypothesis sufficient for lattice algorithms at some polynomial approximation factors; the witnessing algorithm determines the quantitative bounds. We compose unstructured reductions with explicit sample, state-preparation and success conditions, and compare their sufficient guarantees with more than thirty lattice and non-lattice assumptions. We restate the structured state conversion of Wen and Zheng and audit its forward parameter certificate; the printed bound supplies no certificate at the ML-KEM ring and modulus. We use an explicit affine embedding for heuristic gap estimates, explain the lossiness connection from decision NTRU to search Ring-LWE, and distinguish ordinary from module uniqueness. Chen's withdrawn 2024 quantum algorithm for LWE and a proposed repair of its post-processing would, if correct, reach only a many-sample, small-noise LWE regime that the failure-exponent hypothesis already covers for exponents below 1/21/21/2, and no deployed parameter set. Tables separate rigorous consequences, heuristic comparisons and unverified applications, and distinguish solving a proof assumption from attacking a scheme. Classical structural attacks on Classic McEliece, which do not involve DCP but put the concrete security of the scheme under revision, are summarised here and analysed in detail in a companion paper. The survey closes with open questions and a scenario-planning checklist that requires a complete efficient reduction.
Abstract The hidden subgroup problem (HSP) is a cornerstone problem in quantum computing, which captures many problems of interest and provides a standard framework algorithm for their study based on Fourier sampling, one class of techniques known to provide quantum advantage, and which succeeds for some groups but not others. The quantum hardness of the HSP problem for the dihedral group is a critical question for post-quantum cryptosystems based on learning with errors and also appears in subexponential algorithms for constructing isogenies between elliptic curves over a finite field. In this article, we give an updated overview of the dihedral hidden subgroup problem as approached by the “standard” quantum algorithm for HSP on finite groups, detailing the obstructions for strong Fourier sampling to succeed and summarizing other known approaches and results. In our treatment, we “contrast and compare” as much as possible the cyclic and dihedral cases, with a view to determining bounds for the success probability of a quantum algorithm that uses m m coset samples to solve the HSP on these groups. In the last sections, we prove a number of no-go results for the dihedral coset problem (DCP), motivated by a connection between DCP and cloning of quantum states. The proofs of these no-go results are then adapted to give nontrivial upper bounds on the success probability of a quantum algorithm that uses m m coset samples to solve DCP.
We show polynomial-time quantum algorithms for the following problems: (*) Short integer solution (SIS) problem under the infinity norm, where the public matrix is very wide, the modulus is a polynomially large prime, and the bound of infinity norm is set to be half of the modulus minus a constant. (*) Learning with errors (LWE) problem given LWE-like quantum states with polynomially large moduli and certain error distributions, including bounded uniform distributions and Laplace distributions. (*) Extrapolated dihedral coset problem (EDCP) with certain parameters. The SIS, LWE, and EDCP problems in their standard forms are as hard as solving lattice problems in the worst case. However, the variants that we can solve are not in the parameter regimes known to be as hard as solving worst-case lattice problems. Still, no classical or quantum polynomial-time algorithms were known for the variants of SIS and LWE we consider. For EDCP, our quantum algorithm slightly extends the result of Ivanyos et al. (2018). Our algorithms for variants of SIS and EDCP use the existing quantum reductions from those problems to LWE, or more precisely, to the problem of solving LWE given LWE-like quantum states. Our main contribution is solving LWE given LWE-like quantum states with interesting parameters using a filtering technique.
Learning with Errors (LWE) problems are the foundations for numerous applications in lattice-based cryptography and are provably as hard as approximate lattice problems in the worst case. Here we present a reduction from LWE problem to dihedral coset problem(DCP). We present a quantum algorithm to generate the input of the two point problem which hides the solution of LWE. We then give a new reduction from two point problem to dihedral coset problem on D_{{({n^{13})}^{n\log n}}}. Our reduction implicate that any algorithm solves DCP in subexponential time would lead a quantum algorithm for LWE.
It is known that any quantum algorithm for graph isomorphism that works within the framework of the hidden subgroup problem (HSP) must perform highly entangled measurements across Ω(nlog⁡n)\Omega(n\log n)Ω(nlogn) coset states. One of the only known models for how such a measurement could be carried out efficiently is Kuperberg's algorithm for the HSP in the dihedral group, in which quantum states are adaptively combined and measured according to the decomposition of tensor products into irreducible representations. This “quantum sieve” starts with coset states and works its way down toward representations whose probabilities differ depending on, for example, whether the hidden subgroup is trivial or nontrivial. In this paper we show that no such approach can produce a polynomial-time quantum algorithm for graph isomorphism. Specifically, we consider the natural reduction of graph isomorphism to the HSP over the wreath product Sn≀Z2S_n\wr\mathbb{Z}_2Sn​≀Z2​. Using a recently proved bound on the irreducible characters of SnS_nSn​, we show that no algorithm in this family can solve graph isomorphism in less than eΩ(n)\mathrm{e}^{\Omega(\sqrt{n})}eΩ(n​) time, no matter what adaptive rule it uses to select and combine quantum states. In particular, algorithms of this type can offer essentially no improvement over the best known classical algorithms, which run in time eO(nlog⁡n)\mathrm{e}^{O(\sqrt{n\log n})}eO(nlogn​).