PaperlayerView exact revision on arXiv

Source-linked AI summary

Euclidean SVP is NP-hard for Cyclic Lattices

Daqing Wan

arXiv:2609.16711v1cs.CC

TL;DR

Exact Euclidean SVP hardness for general lattices does not by itself establish hardness when cyclic structure must be preserved. This paper gives a deterministic reduction for full-rank cyclic ideals and applies its construction to unrestricted algebraic NTRU-form lattices, proving exact decision NP-completeness and search hardness within those classes.

  • Problem

    General-lattice hardness does not establish hardness for lattices with prescribed cyclic symmetry, where the reduction must preserve that structure.

    Source: §1 · p. 1, §1.3 · p. 4

  • Method

    The reduction encodes assignments in shortest vectors using a relative anchor, finite-field completion, and cyclic correlations that implement a quadratic checker.

    Source: §1 · p. 1

  • Results

    Exact decision SVP is NP-complete for full-rank cyclic ideals and unrestricted algebraic NTRU-form lattices, while exact search is NP-hard under polynomial-time Turing reductions.

    Source: §1.1 · p. 2, §10.1 · p. 34

  • Takeaways & Limitations

    The result establishes deterministic exact-SVP hardness directly for the prescribed cyclic coefficient class rather than deriving it from general-lattice hardness.

    Source: §1 · p. 1, §1.3 · p. 4

    The dimension varies with q, and the constructed cyclic output is not asserted to be a principal ideal.

    Source: §1.1 · p. 2, §9.4 · p. 33

Abstract

from arXiv · show

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.

1 Introduction

The paper establishes deterministic exact-SVP hardness while preserving one-coordinate cyclic symmetry, addressing a gap that general-lattice hardness does not settle. It also outlines an application to unrestricted algebraic NTRU-form lattices.

1.1 The problem and the main result

  • Exact cyclic-ideal decision SVP is NP-complete under deterministic polynomial-time many-one reductions, with hardness for N = q −1 and search-SVP NP-hard under polynomial-time Turing reductions.The reduction preserves one-coordinate cyclic shift invariance.Source: §1 · p. 1, §1.1 · p. 2
  • Exact decision SVP is NP-complete for unrestricted algebraic NTRU-form lattices, with N = q −1; exact search-SVP is NP-hard under polynomial-time Turing reductions.The claim does not cover cryptographically generated keys or their distributions.Source: §1.1 · p. 2

1.2 Why cyclic lattices are an interesting complexity class

  • Cyclic symmetry is computationally substantive: Fourier diagonalization does not remove integral divisibility and compatibility constraints, and cryptographic worst-case-to-average-case reductions do not establish NP-hardness.The paper distinguishes these reductions from a complexity classification of exact SVP.Source: §1.2 · p. 3

1.3 General lattices: hardness, approximation, and derandomization

  • Preserving one-step rotation is the missing ingredient for structured hardness: arbitrary target coordinates, constraint matrices, or independent tensor coordinates generally break that invariance.The construction instead implements constraints through scalar cyclic correlations.Source: §1.3 · p. 4

1.4 Structured lattices and the place of this result

  • The result targets cyclic quotient rings with coefficient norm; it does not establish hardness for full rings of integers or principality of the cyclic output.The proof uses the full quotient ring rather than projecting to a cyclotomic factor.Source: §1.4 · p. 5

1.5 Technical contribution and proof organization

  • The reduction starts from Gap Exact Set Cover and uses a quadratic repair cost that is at least the minimum ordinary set-cover size.A cyclic checker recovers encoded variables and dominates the repair-cost monomials.Source: §1.5 · p. 5
  • Parity sums and finite-field moment constraints force shortest vectors into a binary shape with a unique occupied position that anchors assignments relative to cyclic rotation.A uniform point-counting argument completes each assignment without unwanted checked pairs.Source: §1.5 · p. 5
  • A large scalar map converts the checker value into Euclidean length while keeping longer vectors away from the threshold; a modular-kernel description supports polynomial-time basis construction.The kernel description is reused in the NTRU application.Source: §1.5 · pp. 5–6

2 Outline of the main proof

The proof reduces Gap Exact Set Cover to exact SVP while preserving one-coordinate cyclic symmetry. It encodes assignments in anchored minimum vectors, uses cyclic correlations to reproduce repair cost, and separates YES and NO cases.

2.1 Gap Exact Set Cover and its repair cost

  • Gap Exact Set Cover with fixed factor 3/2 is NP-hard by Micciancio [20, Definition 2.5 and Theorem 2.6]; a NO instance may still have an exact cover of large size.The checker charges for both the chosen subsets and the coverage errors.Source: §2.1 · p. 6
  • A source YES instance has zero repair cost, while a NO instance forces repair cost at least the threshold under the stated promise.The reduction uses these one-way implications; it does not claim the converse for arbitrary repair-cost inputs.Source: §2.1 · p. 7

2.2 The construction in explicit form

  • The repair-cost quadratic specifies the linear, square, and cross-product terms that the cyclic checker must recover.The required correlations correspond to 2di, dj − di, and di + dj; the offsets are chosen so these displacements are distinct and do not wrap around.Source: §2.1 · p. 7, §2.2 · p. 9

2 Outline of the main proof

  • The reduction outputs a cyclic-ideal basis and squared threshold separating the promised source YES and NO cases.Its intermediate checker and final basis are constructed explicitly.Source: §2.2 · p. 8

2.2 The construction in explicit form

  • Parity and moment constraints yield a cyclic ideal whose shortest vectors, after sign and rotation, are binary with one occupied even anchor and h occupied odd positions.The odd support is constrained by the field equations, not chosen arbitrarily.Source: §2.2 · p. 8
  • A shortest vector decodes a nonnegative integer vector through cyclic correlations with the unique anchor, and every Boolean assignment has a clean minimum realization decoding exactly to it.The clean realization sets ydi = ξi and y−di = 0.Source: §2.2 · p. 9

3. Replace the repair polynomial by a cyclic checker, and isolate the checker promise. Substituting z2

The reduction converts repair cost into a shift-invariant checker that is sound on every shortest vector and exact on clean YES completions. A symmetric circulant operator then makes the checker affect ordinary Euclidean length without changing the norm.

3. Replace the repair polynomial by a cyclic checker, and isolate the checker promise. Substituting z2

  • For a NO source instance, every shortest vector has checker value at least τ + 1, since the checker is integer-valued.The soundness argument applies to every shortest y in I.Source: §3 · p. 10
  • A clean completion realizes each Boolean assignment as a shortest ideal vector of squared norm h + 1, with the correlation replacements holding as equalities.This gives completeness for the checker gap.Source: §3 · p. 10
  • On the minimum shell, the repair-cost checker is represented by an integer symmetric circulant operator K, equivalently multiplication by a ring element.The checker’s nonconstant part is already a symmetric circulant quadratic form, and its constant is homogenized using the shell norm.Source: §3 · p. 11

5. Turn the checker quadratic form into ordinary Euclidean length by multiplying

  • Multiplying by g(X) = M + k(X) turns the checker into a cross term in ordinary squared Euclidean length while the scalar term separates longer vectors.The remaining quadratic error is controlled by choosing M sufficiently large.Source: §5 · pp. 11–12
  • The final ideal is the image I′ = TI, so the perturbed length on the old ideal becomes ordinary Euclidean length on the image.The reduction computes a basis of the kernel ideal and applies the multiplication matrix T.Source: §5 · pp. 11–12

3 Parameters and separated offsets

The construction selects polynomially bounded parameters and offsets so that every correlation displacement needed by the checker is distinct, positive, and separated from wraparound.

3 Parameters and separated offsets

  • A prime q in the stated polynomial range and the associated parameters satisfy the bounds needed for collision and counting estimates.Bertrand’s theorem and trial division find q in deterministic polynomial time, and enumerating powers finds α without factoring arbitrary integers.Source: §3 · pp. 12–14
  • The offsets di = 2B0 + 2ηi + 1 make all required displacements distinct and smaller than (q − 1)/2.The set D comprises 2di, dj − di, and di + dj; the displacements therefore do not collide or wrap around.Source: §3 · p. 13
  • The quadratic labels ηi = i + (2r + 1)i2 ensure uniqueness of pair sums and positive differences used in the displacement set.The proof compares linear and quadratic terms to show equality of pair sums or differences forces the same indices.Source: §3 · p. 13

4 The cyclic parity-anchor lattice

Parity and finite-field moment constraints define a full-rank cyclic ideal whose shortest vectors have a rigid, anchored binary form. The proof uses a moment-lattice lower bound to establish the minimum shell and its structure.

4 The cyclic parity-anchor lattice

  • The parity and moment conditions combine into one modular multiplication kernel, which is a full-rank ideal invariant under cyclic shift.The kernel description supports direct basis construction and the NTRU application.Source: §4 · pp. 14–15

4.1 A moment-lattice lower bound

  • Every nonzero vector satisfying the specified Reed–Solomon moment constraints has squared norm at least 2k.This is the moment-lattice lower bound used in the construction.Source: §4.1 · p. 16

4.2 The minimum shell and its anchor

  • The ideal’s minimum squared norm is h + 1, attained exactly by signed binary vectors with vanishing moments and parity weights (h, 1) or (1, h).The unique position in the parity class of weight one is the relative anchor; the other class has h occupied positions.Source: §4.2 · pp. 16–17
  • After sign and cyclic rotation, a minimum vector has its anchor at position 0 and exactly h occupied odd positions, whose selection remains constrained by the moment equations.The odd positions need not be consecutive.Source: §4.2 · p. 17, Figure 1 · p. 17

5 Uniform counting in a quadratic-character coset

The counting argument combines finite-field point-count estimates with a uniform weighted-fiber bound to count supports satisfying prescribed moments. It applies the bounds to labels in a quadratic-character coset while excluding forbidden choices.

5 Uniform counting in a quadratic-character coset

  • To count supports, the argument writes each odd-position label as αx² and excludes zero coordinates, repetitions, and forbidden labels.In the applications, the small-singular-locus bound supports normality and geometric integrality of the relevant schemes.Source: §5 · p. 18, §5.1 · p. 18

5.1 The counting inputs

  • For projective complete intersections, the point-count estimate holds over every extension field; the smooth case uses Deligne, and the singular estimate uses Hooley with Katz’s appendix.The constant in the estimate may depend on the fiber, but not on the extension degree.Source: §5.1 · p. 18

5.2 A uniform weighted-fiber estimate

  • The weighted-fiber coefficient is uniform in the syndrome, permitted weights, q, and extension degree e, with Bs,k < (4k)^s.The estimate assumes q is prime, k ≥ 2, s ≥ k + 2, q > 2(k − 1), and the positive weights sum to less than q.Source: §5.2 · p. 19

1. Geometry of the fiber and its section at infinity. Work over Fq. Let

The weighted equations define a well-behaved fiber and section at infinity: the Jacobian calculation establishes smoothness at infinity, while dimension arguments establish the fiber’s geometric integrality and control its singular locus.

1. Geometry of the fiber and its section at infinity

  • The Jacobian has full rank when there are at least k − 1 distinct nonzero square values, and the grouped-weight argument rules out lower rank.The Vandermonde minor gives the rank in the first case; fewer distinct values would force positive weights below q to vanish in the field.Source: §1 · p. 19
  • Every irreducible component of the projective fiber has dimension d, so the equations have expected codimension and define a complete intersection.The dimension bounds use the component’s hyperplane section at infinity.Source: §1 · p. 20
  • The fiber is geometrically integral, and its singular locus has dimension at most zero.Smoothness along the section at infinity rules out multiple components; Cohen–Macaulayness and generic reducedness establish reducedness.Source: §1 · p. 20
  • Applying the point-count estimate to the fiber and its smooth section at infinity yields an error bound whose constants may depend on the fiber but not on e.Only the exponential rate is needed in the next step.Source: §1 · pp. 19–20

3. A uniform coefficient from the reduced zeta function. The rational function

A reduced-zeta-function argument bounds the cohomological contribution uniformly. The prescribed-subset estimates then count admissible completions and bound the probability that specified free labels are occupied, subject to prescription limits.

3. A uniform coefficient from the reduced zeta function. The rational function

  • The coefficient bound is Bs,k < (4k)^s, obtained by bounding the surviving reciprocal factors of the reduced zeta function and applying the affine complete-intersection estimate.The zeta-function argument uses the holomorphy bound and trace formula before applying the estimate to the affine set.Source: §3 · pp. 20–21

5.3 Prescribed subsets and inclusion probabilities

  • The inclusion bounds apply only when the enlarged prescribed sets satisfy the stated size limits; adding two labels requires original t ≤ r and the total-prescription limit.The proof uses a union bound over single forbidden events; intersections need not be counted.Source: §5.3 · pp. 21–22
  • For the unrestricted tuple count, the count lies between (7/8)q^(s−k+1) and (9/8)q^(s−k+1); each forbidden substitution contributes at most (9/8)q^(s−k).Forbidden events reduce to fibers: zero coordinates delete a variable and its weight; repeated squares merge variables and add their weights; prescribed labels are fixed and their contribution subtracted from the syndrome.Source: §5.3 · p. 22
  • For a uniformly chosen completion, one specified free label is occupied with probability at most 8h/q, and two specified labels with probability at most 16h²/q².These bounds do not assume independence of inclusion events.Source: §5.3 · pp. 21, 23

6 Clean completions for Boolean assignments

Every Boolean assignment has a clean completion in the ideal that is a minimum vector with an anchor at 0. The construction prescribes witness positions, then uses inclusion bounds to find a support with the required checked correlations and no unwanted pairs.

6 Clean completions for Boolean assignments

  • Every Boolean assignment has a clean completion in the ideal, with squared norm h + 1, placing it in the minimum shell with anchor at 0.The probability of finding a completion with no unwanted pair is greater than 3/4.Source: §6 · pp. 24, 26
  • The construction prescribes each positive witness position according to the assignment and fixes every negative witness position to zero.The resulting support family is nonempty, and its binary vectors satisfy the moment equations and have the minimum norm.Source: §6 · pp. 24–25
  • The proof bounds unwanted pairs with one or two free endpoints using the one-label and joint two-label inclusion estimates, then applies a union bound across checked displacements.It does not assume independence of the two endpoint-inclusion events.Source: §6 · p. 25
  • For each checked displacement, the prescribed occupied pair occurs exactly when both corresponding assignment bits are one, with no other occupied pair at that displacement.At 2di and di + dj, no occupied pair occurs.Source: §6 · pp. 23, 26

7 A cyclic checker for the cover cost

The cyclic checker transfers the repair-cost gap to the minimum shell of the constructed lattice. Its decoder turns shortest-vector correlations into a comparison of the source cover cost.

7 A cyclic checker for the cover cost

  • The checker decoder sums the two positions around the anchor, while correlation inequalities bound products between decoded coordinates.The anchor fixes the reference position; the first witness-pair identity is exact, and the other comparisons are inequalities.Source: §7 · p. 26, §7.1 · p. 27

7.1 From the repair polynomial to the checker

  • The intermediate reduction converts Gap Exact Set Cover into a gap in checker value restricted to shortest vectors.In the NO case, every minimum vector has checker value at least tau + 1.Source: §7.1 · p. 27
  • For YES instances, a clean minimum vector decodes to a cover witness of cost at most tau, without requiring an optimal witness.Its correlations make the checker replacements equalities.Source: §7.1 · p. 28

8 From checker values to Euclidean lengths

A symmetric circulant operator represents the checker on the minimum shell, and a large scalar multiplier transfers its gap to ordinary Euclidean lengths. The resulting cyclic ideal preserves the exact YES/NO threshold test.

8.1 The checker as a symmetric circulant operator

  • On the minimum shell, an integer symmetric circulant operator represents the checker as a quadratic form and acts by ring multiplication.The operator need not be positive; its representation is used on the minimum shell.Source: §8.1 · pp. 28–29

8.2 From the checker operator to the final ideal

  • The multiplier adds a large scalar component so the cross term records the checker while longer vectors remain above threshold.The output length combines a baseline, a checker-proportional term, and a controlled quadratic error.Source: §8.2 · pp. 29–30
  • source YES is equivalent to the final ideal having a shortest squared length at most B∗.The output is the full-rank ideal I′ = g(X)I, with the threshold defined in Theorem 8.1.Source: §8.2 · p. 30
  • For YES instances a minimum-shell vector falls below B∗, whereas NO instances exclude every nonzero output vector from the threshold.The construction also makes multiplication injective, yielding a full-rank image ideal with unique preimages.Source: §8.2 · pp. 29–30

9 Basis construction and complexity

The reduction constructs an explicit cyclic-ideal basis and threshold in deterministic polynomial time, then establishes NP membership and exact-search hardness. The result is scoped to the stated cyclic quotient-ring setting and does not provide a constant-factor gap.

9.1 A basis of a modular kernel

  • A modular-kernel basis follows from Smith normal form, with diagonal divisibility conditions yielding an integer basis.The construction uses integer normal form rather than Gaussian elimination over a composite residue ring, and requires no prime factorization of the modulus.Source: §9.1 · p. 31

9.2 Index and output

  • The output basis is obtained by computing the final parameters and applying the multiplier to the base-ideal basis.Its columns generate exactly the image ideal used in Theorem 8.1.Source: §9.2 · p. 32

9.3 Polynomial bit complexity

  • The reduction has polynomial bit complexity, including the Smith normal form transformations and the resulting basis entries.The dimension and coefficient bounds are polynomial in the explicit source input; the construction is deterministic but far too large for practical use.Source: §9.3 · p. 32

9.4 NP membership and the search consequence

  • Exact validity checks and a polynomial-length vector certificate establish that decision-SVP on the constructed instances belongs to NP.The certificate need only show a nonzero lattice vector below threshold, not prove global minimality.Source: §9.4 · p. 32
  • One exact-search call followed by comparing the returned vector’s squared norm with B∗ decides the constructed instance.This yields the stated search hardness under polynomial-time Turing reductions.Source: §9.4 · p. 33
  • The hardness result concerns reducible cyclic quotient rings; it establishes neither hardness over prescribed full rings of integers nor a constant relative separation.The proof’s strict threshold gap does not give hardness within a fixed approximation factor greater than one.Source: §9.4 · p. 33

10 Application to the algebraic class of NTRU-form lattices

The application proves exact Euclidean decision SVP NP-complete for unrestricted algebraic NTRU-form lattices, using tailored hard cyclic ideals rather than claiming every cyclic lattice has the needed representation. Its reduction preserves the threshold while leaving cryptographic NTRU subclasses and key-generation distributions outside the result.

10.1 The target class and the reduction idea

  • The target consists of rank-2N lattices with unweighted coefficient norm, invariant under simultaneous cyclic shifts of both blocks rather than necessarily one shift of all 2N coordinates.The input leaves N, Q, and H unrestricted and imposes no secret-key or key-generation promise.Source: §10.1 · p. 33
  • Exact decision SVP for the algebraic NTRU-form class is NP-complete, with hardness already at N = q −1 and exact search-SVP NP-hard under polynomial-time Turing reductions.The result concerns the unrestricted algebraic class, not cryptographically generated keys.Source: §10.1 · p. 34
  • The reduction adapts the particular hard ideals so each is the kernel of one modular convolution, then uses a threshold-preserving NTRU embedding.The application does not assert that every cyclic lattice admits the needed congruence representation.Source: §10 · p. 33, §10.1 · p. 34

10.2 A congruence-preserving hard image ideal

  • The modified multiplier is congruent to the identity modulo q(h^2 −1), making J a full-rank cyclic ideal while preserving the source YES/NO threshold equivalence.The proof establishes a strict decision gap, with every off-shell vector mapping above the threshold.Source: §10.2 · pp. 34–35

10.3 A single annihilator for the hard image ideal

  • A single modular-kernel description of J is obtained by imposing both membership in T0RN and membership in the base ideal I.The proof identifies their intersection as exactly J.Source: §10.3 · p. 36

10.4 Embedding the hard kernel in NTRU form

  • In the NTRU embedding, every vector within squared threshold b has vanishing second block and corresponds exactly to a nonzero vector of J with the same squared length.The embedding scales the public polynomial and modulus by b + 1 so any nonzero scaled second block exceeds the threshold.Source: §10.4 · p. 37

10.5 Proof of the application and complexity

  • The reduction is deterministic polynomial time, and a nonzero integer pair within the threshold is a polynomial-size certificate checked by exact cyclic convolution and norm comparison.One exact search-oracle call followed by a squared-norm comparison yields the search consequence.Source: §10.5 · pp. 37–38

10.6 What the application does not establish

  • The construction's shared factor forces short vectors' second block to vanish, but the theorem establishes no hardness for cryptographic NTRU key-generation subclasses or distributions.The constructed public polynomial is not a unit; the result is neither an average-case security theorem nor hardness of secret-key recovery.Source: §10.6 · p. 38

Related papers

Loading 2609.16711v1…