Source-linked AI summary
SVP Is NP-Hard for Some Rank-2 Cyclotomic Modules
Jiaqi Liu, Yansong Feng, Yanbin Pan
TL;DR
The paper asks whether Euclidean SVP is NP-hard for rank-two modules over cyclotomic rings and answers affirmatively for full-rank free submodules. It reduces X3C using binary representatives in ideal cosets, a Gauss-sum checker, and a second module coordinate to control unintended ring multiples, obtaining an NP-completeness equivalence and search-SVP hardness.
Problem
The paper asks whether Euclidean SVP is NP-hard for rank-two modules over cyclotomic rings, including the challenge posed by closure under multiplication by O_K.
Method
The reduction uses binary representatives in fixed ideal cosets, a checker whose squared norm encodes X3C residuals, and a second module coordinate with ideal-coset separation.
Results
The construction establishes λ1(M)^2 ≤ S exactly when the X3C instance is positive, yielding NP-completeness for the decision problem and NP-hardness of search-SVP under polynomial-time Turing reductions.
Takeaways & Limitations
Euclidean SVP is NP-complete on full-rank free submodules of O_K^2 even with fixed module rank two.
Takeaways & Limitations
The result varies the cyclotomic ring with q and does not establish hardness for a single fixed ring, the power-of-two family, average-case instances, or cryptographic security reductions.
Abstract
from arXiv · showhide
Let $q$ range over primes congruent to $3$ modulo $4$. 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]$. 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\equiv3\pmod4$, two integral generators whose $2\times2$ 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.
1 Introduction
The paper establishes deterministic NP-completeness of Euclidean SVP for rank-two cyclotomic modules via a reduction from X3C. Its construction addresses unintended shorter vectors from ring multiplication using ideal-coset representatives, an X3C checker, and module-coordinate separation.
- The paper answers affirmatively whether Euclidean SVP is NP-hard for rank-two modules over cyclotomic rings.
- The decision problem is NP-complete under deterministic polynomial-time many-one reductions from Exact Cover by 3-Sets.Each instance uses a prime q ≡3 (mod 4), two generators in O_K^2 with nonzero determinant, and an integer squared threshold.
- Search-SVP is NP-hard under polynomial-time Turing reductions, while the underlying Z-lattice has rank 2(q − 1) as q varies.
- The reduction embeds X3C assignments into binary representatives whose evaluations lie in a fixed coset of a principal cyclotomic ideal.Bennett–Peikert Reed–Solomon lattices provide the ideal map, while Wan’s point-count estimate supplies many representatives for every assignment.
- A checker converts the X3C residual Aξ − 1_M into a canonical squared norm, with clean representatives attaining the baseline and negative instances incurring an additive gap of 2.The checker norm is B0 for an exact cover and at least B0 + 2 for every binary coefficient vector in a negative instance.
2 Preliminaries
The preliminaries define Euclidean lattices, cyclotomic module lattices, and X3C, then introduce Sidon sequences and uniform power-sum estimates used later.
- Euclidean lattices: Exact decision-SVP asks whether a lattice contains a nonzero vector below a squared-norm threshold, while search-SVP asks for a shortest nonzero vector.The decision problem is in NP because a short integer coefficient vector provides a polynomial-length certificate checkable with exact arithmetic.
- Cyclotomic fields and module lattices: The cyclotomic setup uses K = Q(ζ), O_K = Z[ζ], π = 1 −ζ, and total ramification (q) = (π)^{q−1}.Roots of unity act isometrically under the canonical norm, preserving distances.
- Cyclotomic fields and module lattices: A full-rank free O_K-module generated by s K-linearly independent vectors has module rank s and Z-rank s(q −1).For submodules of O_K^s, full rank is equivalent to finite index.
- X3C and Sidon sequences: X3C asks whether a selection vector chooses three-element sets covering every universe element exactly once.The incidence matrix records set membership, and X3C is NP-complete.
- X3C and Sidon sequences: A Sidon sequence provides distinct indices whose nonzero ordered differences are all distinct, with a deterministic construction whose largest entry is O(n^2).These indices are used to encode selection bits without repeated differences.
- Power-sum estimates: Wan’s uniform point-count estimates bound solutions to prescribed power-sum equations, including solutions with collisions or coordinates fixed to specified field elements.The estimates are uniform in the prescribed power-sum vector and relevant coordinate choices.
3 Reed–Solomon lattices and ideal cosets
The section maps lifted Reed–Solomon lattices to principal cyclotomic ideals and proves that their cosets contain abundant binary representatives with strong norm separation.
- Ideal cosets: Evaluation at ζ embeds binary vectors into O_K, while designated coordinates store the X3C selection bits in a longer fixed-weight vector.Every selection vector must extend to a weight-h binary vector lying in one ideal coset independent of the selection.
- Reed–Solomon lattices and ideals: The lifted Reed–Solomon lattice maps to the principal ideal a_q,k = π^kO_K through evaluation at ζ.The kernel of evaluation is generated by the cyclotomic polynomial, and total ramification identifies the image with (π^k).
- Binary representatives: Every ideal-coset element has a unique integral coefficient representative with prescribed syndrome and coefficient sum.The representative is obtained by adjusting a solution by an integer multiple of the all-ones vector, which has zero evaluation.
- Norm bounds: The canonical norm of every binary weight-h representative is H = h(q −h), whereas every nonzero ideal element has squared norm at least L.This transfers the Reed–Solomon minimum bound to the cyclotomic ideal.
- Binary representatives: For every sufficiently large q, prescribed syndromes and coordinate assignments of size at most T admit many binary representatives in the corresponding ideal coset.The count follows from uniform power-sum estimates after excluding collisions and entries in the fixed-coordinate set.
4 The X3C checker
The checker encodes X3C selection constraints into a squared norm while carefully separating witness and bad correlations. Clean binary representatives make the error term vanish, yielding a canonical value tied to exact covers.
- Checker construction: The checker maps a binary representative x to a value Uv_x − V whose squared norm records the residual Aξ − 1_M plus a nonnegative error term.The baseline B0 is independent of x, while E(x) ≥ 0 collects correlations not determined by the selection vector.
- Encoding X3C: The selection bit ξ_j records whether set C_j is chosen, and exact cover is equivalent to every row sum s_i equaling 1.Each s_i counts selected sets containing universe element i.
- Offset separation: Witness offsets use differences between distinct witness positions, while bad offsets use cross-row differences and sums of offsets.The construction assigns β_i = τi and d_ij = β_i − α_j, then separates the resulting offset families modulo q.
- Offset separation: 0 is not a bad offset, bad and witness offsets are disjoint, and the bad-offset set has size O(n^2).These properties prevent unintended correlations from interfering with the witness products.
- Norm formula: For an exact cover, the checker attains the baseline squared norm B0; for arbitrary binary representatives, the error term can only increase the norm.The Gauss-sum construction supplies U with embedding-wise norm at least one, preserving the canonical norm contribution.
- Clean completions: A clean completion satisfies the prescribed witness correlations and zeroes all bad-offset correlations, forcing E(x) = 0.Point-count and union-bound arguments guarantee a clean completion for every selection vector under the stated parameter conditions.
5 The rank-two reduction
The reduction embeds the X3C checker into a rank-two cyclotomic module and uses a scaled second coordinate to separate intended short vectors from all others. This establishes an exact YES–NO threshold gap in polynomial time.
- Module construction: The module uses the checker coordinate together with a second coordinate scaled by Γ, with generators formed from the ideal, center, and checker elements.The generator matrix has nonzero determinant, making the resulting submodule full-rank and free of module rank two.
- Completeness: The completeness threshold is S = B0 + F, where F is the second-coordinate contribution of a root of unity.For an exact cover, a clean completion yields a module vector with squared norm exactly S.
- Soundness: Every nonzero module vector in a negative X3C instance has squared norm greater than S, covering zero, root-of-unity, and non-root-of-unity second-coordinate cases.The proof combines checker lower bounds, stability estimates, coset separation, and the second-coordinate scale.
- Complexity and encoding: The constructed module has rank two over O_K and rank 2(q − 1) as a Z-lattice.The growing Z-rank reflects the cyclotomic embedding while the module rank remains fixed.
- Complexity and encoding: The reduction is deterministic and polynomial-time, outputs integral generators with nonzero determinant, and preserves the exact YES–NO equivalence.Denominator clearing scales norms and thresholds uniformly, while coefficient and encoding lengths remain polynomially bounded.
- Consequences: At most one oracle call to decision-SVP decides X3C, yielding the claimed Turing hardness for search-SVP.The construction therefore supports the paper’s additional search-SVP hardness conclusion.