Metraipolis › archive › dc_1569a8bf4e51
Cyclotomic Cosets: Hidden Subgroup and Quantum Sieving Algorithm for Prime-Power Moduli — arXiv:2609.34996
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.34996
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T22:35:08.576Z
- SHA-256 of the archived text
16fcee622b32a93e442efd1aa5934f66223aee7c1e2b6021633ea4a8b895690b- Stable URL of this page
https://metraipolis.com/documento/dc_1569a8bf4e51
How to cite
Cyclotomic Cosets: Hidden Subgroup and Quantum Sieving Algorithm for Prime-Power Moduli — arXiv:2609.34996 — arXiv (en), https://arxiv.org/abs/2609.34996 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_1569a8bf4e51 (Metraipolis archive dc_1569a8bf4e51, sha256 16fcee622b32a93e442efd1aa5934f66223aee7c1e2b6021633ea4a8b895690b)
BibTeX
@misc{dc1569a8bf4e51,
title = {Cyclotomic Cosets: Hidden Subgroup and Quantum Sieving Algorithm for Prime-Power Moduli — arXiv:2609.34996},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.34996},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_1569a8bf4e51; sha256 16fcee622b32a93e442efd1aa5934f66223aee7c1e2b6021633ea4a8b895690b},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.34996. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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.
Tema degli esploratori: fiducia digitale e crittografia (retro-catalogo arXiv: annunci del 2026-09-29 in cs.CR).
Categorie arXiv: Quantum Physics (quant-ph) ; Cryptography and Security (cs.CR).
Pagina del lavoro: https://arxiv.org/abs/2609.34996 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T22:13:03.798Z dalla pagina https://arxiv.org/catchup/cs.CR/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).