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

• The paper answers affirmatively whether Euclidean SVP is NP-hard for rank-two modules over cyclotomic rings.Source: §1 · p. 2, §1.1 · p. 3
• 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.Source: §1.1 · p. 3
• Search-SVP is NP-hard under polynomial-time Turing reductions, while the underlying Z-lattice has rank 2(q − 1) as q varies.Source: §1.1 · p. 3
• 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.Source: §1.2 · pp. 3–4
• 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.Source: §1.2 · pp. 3–4

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.Source: §2.1 · p. 6

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.Source: §2.2 · pp. 6–7
• 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.Source: §2.2 · p. 7

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.Source: §2.3 · p. 8
• 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.Source: §2.3 · p. 8

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.Source: §2.4 · p. 9

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.Source: §3 · p. 9

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).Source: §3.1 · pp. 10–11

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.Source: §3.2 · p. 11

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.Source: §3.1 · p. 10, §3.2 · p. 12

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.Source: §3.2 · pp. 12–13

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.Source: §4 · p. 16, §4.2 · p. 19

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.Source: §4.1 · p. 16

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.Source: §4.1 · p. 16
• 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.Source: §4.1 · pp. 16–17

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.Source: §4.2 · pp. 17–18

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.Source: §4.3 · pp. 20–21

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.Source: §5 · p. 22, §5.3 · p. 25

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.Source: §5.1 · p. 22, §5.2 · p. 24

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.Source: §5.2 · pp. 23–24

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.Source: §5.3 · p. 25, §5.5 · p. 27
• 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.Source: §5.3 · pp. 24–25, §5.5 · p. 27

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.Source: §5.5 · p. 28