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.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.3769May 16, 20130 citations

A subexponential-time quantum algorithm for LWE problem

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

May 16, 20130 citations

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

Mathias Boucher, Pierre-Alain Fouque, Yixin Shen

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

quant-pharXiv:2609.34996Sep 29, 20260 citations

Quantum Cryptography at the Computational Frontier

Romain Alléaume

Jun 1, 20180 citations

ζ_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.