Paper 2026/2861

$\mathsf{SVP}_\infty$ Is NP-Hard for Power-of-two Cyclotomic Ideals

Yansong Feng, Academy of Mathematics and Systems Science
Jiaqi Liu, Academy of Mathematics and Systems Science
Hengyi Luo, Academy of Mathematics and Systems Science
Yanbin Pan, Academy of Mathematics and Systems Science
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.