Paper 2026/2861
$\mathsf{SVP}_\infty$ Is NP-Hard for Power-of-two Cyclotomic Ideals
Abstract
We prove that exact decision-$\mathsf{SVP}$ in the coefficient $\ell_\infty$-norm is $\mathsf{NP}$-complete for principal ideals and free modules of rank two over the cyclotomic rings $R_n=\mathbb{Z}[X]/(X^n+1)$, where $n$ ranges over powers of two. For each case, we give a deterministic polynomial-time many-one reduction from the Subset Sum problem. For an instance with $s$ positive input integers, the output lattice has dimension $O(s)$. A solution to the original Subset Sum instance can be recovered in polynomial time from any nonzero output lattice vector of norm at most the specified bound. We also transfer these reductions from $R_n$ to the power-of-two cyclic rings $S_{2n}=\mathbb{Z}[X]/(X^{2n}-1)$. This gives $\mathsf{NP}$-completeness of decision-$\mathsf{SVP}$ in the coefficient $\ell_\infty$-norm for principal ideals and free modules of any fixed positive rank over these rings.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- shortest vector problemideal latticesmodule latticescyclotomic ringsinfinity normNP-completeness
- Contact author(s)
-
fengyansong @ amss ac cn
ljqi @ mail nankai edu cn
luohengyi @ amss ac cn
panyanbin @ amss ac cn - History
- 2026-11-13: approved
- 2026-11-10: received
- See all versions
- Short URL
- https://ia.cr/2026/2861
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/2861,
author = {Yansong Feng and Jiaqi Liu and Hengyi Luo and Yanbin Pan},
title = {$\mathsf{{SVP}}_\infty$ Is {NP}-Hard for Power-of-two Cyclotomic Ideals},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/2861},
year = {2026},
url = {https://eprint.iacr.org/2026/2861}
}