CS Paper Radar

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

Jiaqi Liu, Yansong Feng, Yanbin Pan

cs.CC cs.CR ·submitted 2026-09-01 16:04 UTC · v2
theory

Abstract

Let $q$ be an odd prime. Let $ζ_q$ be a primitive $q$th root of unity, and put $K=\mathbb{Q}(ζ_q)$, with ring of integers $\mathcal{O}_K=\mathbb{Z}[ζ_q]$. As $q$ ranges over odd primes, we prove that the decision version of the Shortest Vector Problem ($\mathsf{SVP}$) in the canonical $\ell_2$-norm is $\mathsf{NP}$-complete on full-rank free submodules of $\mathcal{O}_K^2$ by giving a deterministic polynomial-time many-one reduction from Exact Cover by 3-Sets (X3C). The module rank is fixed at two. 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, we construct a checker whose canonical squared norm encodes the X3C equations, with a controlled nonnegative error term. Third, the checker and a second module coordinate combine with a separation bound for ideal cosets to rule out short vectors in NO instances. Each constructed instance consists of an odd prime $q$, two integral generators whose $2\times2$ generator matrix has nonzero determinant, and an integer squared threshold. The construction also gives $\mathsf{NP}$-hardness of search-$\mathsf{SVP}$ under deterministic polynomial-time Turing reductions with at most one oracle call.

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.CC ·2026-11-10 ·Yansong Feng, Jiaqi Liu, Hengyi Luo, Yanbin Pan
theory similarity 0.75
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.

0.19

Euclidean SVP is NP-hard for Cyclic Lattices

cs.CC ·2026-09-15 ·Daqing Wan
theory similarity 0.66
Abstract · 39 pages

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.

0.38

Polynomial-Factor Deterministic NP-Hardness for SVP in Every $\ell_p$ Norm with $p>2$

cs.CC ·2026-08-14 ·Isaac M Hair, Amit Sahai
theory similarity 0.63
Abstract

We prove that for every constant $2<p<\infty$, the shortest vector problem in the $\ell_p$ norm is NP-hard to approximate within a polynomial factor under a deterministic reduction. More precisely, for lattices of rank $M$, we obtain a factor of $M^\varepsilon$ for every constant $0<\varepsilon<\min\{(p-2)/(4p),1/8\}$. For $p=\infty$, the same holds for every constant $0<\varepsilon<1/8$. Our reduction adapts OpenAI's encoding of a satisfying assignment for the closest vector problem ("Ten Advances in Mathematics and Theoretical Computer Science"). The encoding has one block of coordinates for each evaluation of a polynomial, with one position for each possible value. We allow the entries in a block to be arbitrary field elements, which can cancel when we take weighted sums of powers of these values. We show that on an unsatisfiable formula, a nonzero codeword with small support must have many nonzero entries in each block it uses. Applying a Hadamard matrix to each block, as in a work by Hair and Sahai (STOC 2026), gives the gap in vector length. The main results of this paper were discovered by Codex / ChatGPT 5.6 Sol Ultra using harness components from the UCLA Moonshot Harness Project, in response to a general strategy suggested by the authors. See the end of the introduction for a discussion.

0.32

CVP Is NP-Complete for Principal Cyclotomic Ideals

cs.CC ·2026-08-24 ·Jiaqi Liu, Yansong Feng, Yanbin Pan
theory similarity 0.61
Abstract

We prove that exact Euclidean decision-CVP is $\mathsf{NP}$-complete on the coefficient lattices of nonzero principal ideals in the power-of-two cyclotomic rings $R_d:=\mathbb{Z}[y]/(y^d+1)$. Our deterministic reduction from Exact Cover by 3-Sets (X3C) produces a target and a squared threshold $Δ$ such that the closest squared distance is exactly $Δ$ in YES instances and at least $Δ+4$ in NO instances. This also implies $\mathsf{NP}$-hardness of exact search-CVP under polynomial-time Turing reductions. We also transfer the resulting principal-ideal CVP instances to full-rank principal ideals of the cyclic quotient ring $\mathbb{Z}[X]/(X^D-1)$, where $D:=2d$. Their coefficient lattices are invariant under cyclic coordinate shifts. The lift preserves principality and multiplies corresponding squared distances by eight. Thus, on principal cyclic ideal lattices, exact decision-CVP is $\mathsf{NP}$-complete and exact search-CVP is $\mathsf{NP}$-hard. We also obtain uniformly computable fixed cyclotomic and cyclic families in which only the target and threshold depend on the X3C collection. Consequently, a polynomial-time solution to exact decision-CVPP on either family would imply $\mathsf{NP}\subseteq\mathsf{P}/\mathrm{poly}$ and collapse the polynomial hierarchy to $Σ_2^{\mathsf{P}}$. To our knowledge, the cyclic results answer Micciancio's questions of whether exact decision-CVP is $\mathsf{NP}$-hard on cyclic lattices and on a fixed family of cyclic lattices, even when restricted to full-rank principal cyclic ideals. Finally, under the coefficient embedding, we prove that exact decision-module-SIVP is $\mathsf{NP}$-complete on free rank-two modules over the same cyclotomic rings.

0.38

NP-hardness of ideal lattice problems

cs.CC math.NT ·2026-09-14 ·Daniel E. Martin
similarity 0.60
Abstract · 27 pages, 2 figures

We establish the worst-case hardness of several ideal lattice problems (including SVP and CVP) in the $\ell_2$ norm by providing a dimension-preserving, deterministic polynomial time reduction from their generic lattice versions. The reduction constructs an ideal lattice in the canonical embedding of a number field that approximates some input lattice up to scaling and orthogonal transformation. The integers defining the ideal and the ambient number ring, in particular its discriminant, are all polynomial in bit length relative to the generic input lattice. Furthermore, the ideal is invertible, the ring is monogenic, and the number field is totally real. If the number ring is also required to be a full ring of integers, the reduction conjecturally succeeds in bounded-error quantum polynomial time.

0.33

Weak Unit Reducibility of the Eleventh Cyclotomic Field

cs.CR math.NT ·2026-11-11 ·Yiyang Chang
theory similarity 0.59
Abstract

We prove that the cyclotomic field $K_{11}=\mathbb{Q}(ζ_{11})$ is unit reducible but not strongly unit reducible. So every nonzero principal fractional ideal of $K_{11}$ has a generator that is a shortest nonzero vector. For $I=h\mathcal{O}_{K_{11}}$, every shortest nonzero vector $α\in I$ satisfies $N_{K_{11}/\mathbb{Q}}(α/h)\in\{1,11\}$. The proof uses Sigrist's Hermite bound for cyclic forms and an averaging identity for cyclotomic units. For principal ideals in $K_{11}$, ideal-SVP and the shortest-generator problem are polynomial-time equivalent.

0.45

Admissible sets of integers in imaginary quadratic fields of class number 1

cs.DM math.NT ·2026-10-25 ·Daniel Shiu
theory similarity 0.58
Abstract · 25 pages, 8 figures

Let $\mathcal O_K$ be the ring of integers of a number field $K$. A finite subset $\mathcal H=\{η_1,\ldots,η_k\}\subset\mathcal O_K$ is said to be \emph{admissible} if for every prime ideal $\mathfrak p$ in $\mathcal O_K$, the reductions of the $η_i$ modulo $\mathfrak p$ do not represent every residue class. The diameter of a finite subset $S$ of $\mathcal O_K$ is defined to be \[\mathrm{diam}(S):= \max_{η_i,η_j\in S:η_i\neqη_j}|\mathcal N(η_i-η_j)|\] where $\mathcal N$ denotes the norm down to the rational field. This paper computationally investigates admissible subsets of rings of integers in imaginary quadratic fields of class number 1 (such as the Gaussian integers or the Eisenstein integers) that are large relative to their diameter. The motivation is twofold. Firstly, there is the improvement of results analogous to the question of an upper bound for the least gap between large rational primes, which has been one of the great number theoretic successes of the twenty-first century. A second motivation is that there is the opportunity to disprove a variation of the second Hardy-Littlewood conjecture. The calculations in the paper provide new records on the smallest distance between primes in the fields in question, and explicit counter-examples to a generalisation of the second Hardy-Littlewood conjecture in all bar one of the fields.

0.30

Evasive subspaces, minimal rank-metric codes and subspace designs via auxiliary fields

cs.IT math.CO ·2026-11-05 ·Alessandro Giannoni
similarity 0.58
Abstract · 33 pages

We extend the auxiliary-field method for scattered subspaces to evasive subspaces and subspace designs. For $1\le h\le k<hn$ and coprime $h,k+1$ with $n(k-h+1)\ge k+1$, we construct spanning $(h,k)$-evasive $\mathbb{F}_q$-subspaces of $\mathbb{F}_{q^n}^r$ of dimension $rn(k-h+1)/(k+1)$ in every sufficiently large admissible ambient dimension, with a threshold independent of $q$. When $k<n$, this dimension is maximum. The proof combines an intersection lemma, a rank-support density inequality, scalar orbit counting, and a profile preserved by direct sums. The coding consequences include, for every fixed odd extension degree $m\ge3$ and every sufficiently large $K$, minimal rank-metric codes of optimal length $2K$ with first two generalized weights $(m+1)/2$ and $m+1$. For these codes the stable profile is equivalent to minimality with the largest possible minimum distance; for even $m$ the analogous class consists of minimal MRD codes. More generally, for $1\leτ\le m-2$ and $\gcd(m,τ+1)=1$, we obtain nondegenerate $τ$-minimal codes of length $(τ+1)K$ for every sufficiently large $K$, uniformly in $q$. We also construct maximum $h$-designs whose number of members grows exponentially with the ambient dimension at fixed $q,n,h$, and the associated maximum sum-rank distance (MSRD) codes with a growing number of equal long blocks. In extension degree five, the ordinary and $2$-minimal constructions hold for every $q$ and every $K\ge32$ and $K\ge59$, respectively.

0.09