Metraipolis › archive › dc_e1d41aebd9dd
Euclidean SVP is NP-hard for Cyclic Lattices — arXiv:2609.16711
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.16711
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-15T22:00:18.056Z
- SHA-256 of the archived text
6b4c7d2f054b7f53495f01d992e2eb3aa8ca3a8d900eec0f0949365c37ccd997- Stable URL of this page
https://metraipolis.com/documento/dc_e1d41aebd9dd
How to cite
Euclidean SVP is NP-hard for Cyclic Lattices — arXiv:2609.16711 — arXiv (en), https://arxiv.org/abs/2609.16711 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e1d41aebd9dd (Metraipolis archive dc_e1d41aebd9dd, sha256 6b4c7d2f054b7f53495f01d992e2eb3aa8ca3a8d900eec0f0949365c37ccd997)
BibTeX
@misc{dce1d41aebd9dd,
title = {Euclidean SVP is NP-hard for Cyclic Lattices — arXiv:2609.16711},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.16711},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e1d41aebd9dd; sha256 6b4c7d2f054b7f53495f01d992e2eb3aa8ca3a8d900eec0f0949365c37ccd997},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.16711. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We prove that exact Euclidean SVP is NP-hard under deterministic polynomial-time many-one reductions for full-rank cyclic integer lattices, equivalently full-rank ideals of $R_N:=\mathbb{Z}[X]/(X^N-1)$ in the coefficient norm. Hardness holds with $N=q-1$ for a varying odd prime $q$. As an application, we prove the same hardness for the algebraic class of NTRU-form lattices $\{(x,z)\in R_N^2:Hx\equiv z\pmod{QR_N}\}$, where $H,Q$ are unrestricted inputs. The decision problems are NP-complete, and the exact search problems are NP-hard under polynomial-time Turing reductions. No hardness claim is made for cryptographic NTRU parameter subclasses or key-generation distributions.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-16 in cs.CC).
Categorie arXiv: Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2609.16711 — 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-15T21:49:12.505Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-09-16?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).