SVP Is NP-Hard for Some Rank-2 Cyclotomic Modules

Abstract

Let $q$ range over primes congruent to $3$ modulo $4$. Let ${\zeta }_q$ be a primitive $q$th root of unity, and put $K=\mathbb{Q}({\zeta }_q)$, with ring of integers ${\mathcal{O}}_K=\mathbb{Z}[{\zeta }_q]$. We prove that the decision version of the Shortest Vector Problem ($\mathrm{SVP}$) in the ${\ell }_2$-norm is $\mathrm{NP}$-complete on full-rank free submodules of ${\mathcal{O}}_K^2$ by a deterministic polynomial-time many-one reduction from Exact Cover by 3-Sets (X3C). The module rank is fixed at two. As a $\mathbb{Z}$-lattice, the module has rank $2(q-1)$, which grows with $q$. The main obstacle is closure under the action of ${\mathcal{O}}_K$. A module containing a nonzero vector also contains every scalar multiple of that vector by a nonzero element of ${\mathcal{O}}_K$, and some of these multiples may be shorter. Three ideas overcome this obstacle. First, we map the Bennett--Peikert Reed--Solomon lattice to a principal cyclotomic ideal and use Wan's point-count estimates to prove that a coset of this ideal contains many binary coefficient representatives. Second, a checker based on a quadratic Gauss sum turns the X3C equations into a canonical squared norm. Third, the checker and a second module coordinate combine with a separation bound for ideal cosets to rule out every unintended vector created by the ${\mathcal{O}}_K$-action. Each constructed instance consists of a prime $q\equiv 3(\mathrm{mod}4)$, two integral generators whose $2\times 2$ generator matrix has nonzero determinant, and an integer squared threshold. The construction also gives $\mathrm{NP}$-hardness of search-$\mathrm{SVP}$ under polynomial-time Turing reductions.