Source-linked AI summary
Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors
Ishay Haviv, Oded Regev
TL;DR
The paper improves known hardness results for approximating SVP. It uses tensor products of lattices, analyzed through the behavior of Khot’s instances, to obtain stronger hardness factors under stated complexity assumptions.
Problem
Known hardness results for lattice problems motivate improving the best hardness factor for SVP, which has cryptographic relevance.
Method
The proof boosts Khot’s basic SVP instances using standard tensor products of lattices and analyzes their behavior under tensorization.
Results
2^{(log n)^{1−ε}} hardness holds for SVP in the ℓ_p norm unless NP ⊆ RTIME(2^{poly(log n)}), while n^{c/log log n} hardness holds unless NP ⊈ RSUBEXP.
Takeaways & Limitations
The paper establishes stronger SVP hardness factors under randomized quasipolynomial-time reductions than the previously known result.
Takeaways & Limitations
The stronger n^{c/log log n} result relies on NP ⊈ RSUBEXP, and known hardness proofs for SVP in ℓ_p norms with p<∞ use randomized reductions.
Abstract
from arXiv · showhide
$ \newcommand{\SVP}{\mathsf{SVP}} \newcommand{\NP}{\mathsf{NP}} \newcommand{\RTIME}{\mathsf{RTIME}} \newcommand{\RSUBEXP}{\mathsf{RSUBEXP}} \newcommand{\eps}ε \newcommand{\poly}{\mathop{\mathrm{poly}}} $We show that unless $\NP \subseteq \RTIME (2^{\poly(\log{n})})$, there is no polynomial-time algorithm approximating the Shortest Vector Problem ($\SVP$) on $n$-dimensional lattices in the $\ell_p$ norm ($1 \leq p< \infty$) to within a factor of $2^{(\log{n})^{1-\eps}}$ for any $\eps > 0$. This improves the previous best factor of $2^{(\log{n})^{1/2-\eps}}$ under the same complexity assumption due to Khot (J. ACM, 2005). Under the stronger assumption $\NP \nsubseteq \RSUBEXP$, we obtain a hardness factor of $n^{c/\log\log{n}}$ for some $c> 0$. Our proof starts with Khot's $\SVP$ instances that are hard to approximate to within some constant. To boost the hardness factor we simply apply the standard tensor product of lattices. The main novelty is in the analysis, where we show that the lattices of Khot behave nicely under tensorization. At the heart of the analysis is a certain matrix inequality which was first used in the context of lattices by de Shalit and Parzanchevski (2006).
1 Introduction
The paper improves hardness-of-approximation results for SVP by showing that Khot’s lattice instances behave well under standard tensor products. This yields stronger factors under randomized quasipolynomial-time reductions and related complexity assumptions.
- Background: SVP asks for the shortest nonzero vector in a lattice, while CVP asks for the closest lattice point to a target.Lattice problems are studied partly because their hardness supports cryptographic constructions.
- Prior work: Khot’s prior result gave SVP hardness factor 2^(log n)^(1/2−ε) under randomized quasipolynomial-time reductions for 1 < p < ∞.The result also established hardness for arbitrarily large constants under randomized reductions.
- Results: The paper’s main result improves the best known SVP hardness factor for every finite p.For p = ∞, a stronger result was already known, and the constant-factor case was previously proved by Khot.
- Results: 2^(log n)^(1−ε) is unattainable by polynomial-time SVP approximation algorithms unless the stated randomized quasipolynomial-time complexity containment holds.This applies to n-dimensional lattices in the ℓ_p norm for every ε > 0.
- Results: n^(c/log log n) is likewise hard under the stronger assumption NP ⊈ RSUBEXP.The paper states this for some c > 0.
- Techniques: The proof starts from Khot’s constant-hard instances and applies the standard k-fold tensor product, producing dimension n^O(k) and hardness 2^Ω(k).The key contribution is proving that Khot’s basic instances behave well under standard tensorization, using a matrix-inequality-based analysis related to de Shalit and Parzanchevski.
- Open questions: Open questions include surpassing the n^(c/log log n) hardness factor and weakening the assumption behind that result to P ≠ NP.For finite p, known hardness proofs still use randomized reductions, making deterministic reductions challenging.
2 Preliminaries
This section defines lattices, norms, shortest-vector parameters, GapSVP, and tensor products. It emphasizes that tensor-product shortest vectors require careful analysis because the natural lower bound can be strict.
- Lattices: A lattice is a discrete additive subgroup of R^n generated by integer combinations of linearly independent vectors, and a basis may be represented as a matrix.Different bases can generate the same lattice; unimodular transformations preserve the generated lattice.
- Norms and shortest vectors: For 1 ≤ p < ∞, the ℓ_p norm is defined from coordinatewise pth powers, while ℓ_∞ uses the maximum coordinate magnitude.
- Norms and shortest vectors: The shortest-vector parameter λ_1^(p)(L) is the ℓ_p norm of a shortest nonzero lattice vector, equivalently the minimum distance between distinct lattice points.Successive minima generalize this parameter by requiring linearly independent lattice points inside an ℓ_p ball.
- GapSVP: GapSVP_p is a promise problem distinguishing lattices with λ_1^(p)(L) ≤ γ·s from those with λ_1^(p)(L) > s.
- Tensor products: The tensor product L_1 ⊗ L_2 is generated by pairwise tensor products of basis vectors and can be represented by an n_1n_2-dimensional lattice.Vectors in the product can be viewed as matrices, and the tensor product of vectors corresponds to an outer-product matrix.
- Tensor products: For tensor products, shortest-vector norms satisfy the product upper bound, but this inequality can be strict for lattices unlike the corresponding equality for linear codes.Self-dual lattice examples show that tensorization can produce substantially shorter vectors than multiplying the individual shortest-vector lengths.
3 Proof of results
The proof reduces SAT to GapSVP through Khot’s structured instances, then amplifies the gap by tensorizing lattices and analyzing how NO instances behave under tensor products. Appropriate choices of the tensor power yield the paper’s hardness results across ℓ_p norms.
- Main reduction: Theorem 3.1 gives a randomized reduction from SAT with input size n and integer k to GapSVP_p in dimension n^Ck, with gap γ = 2^-ck.The reduction runs in time polynomial in n^Ck and has two-sided error probability 1/10.
- Norm reduction: For any 1 ≤ p ≤ ∞, the general norm case follows from a randomized reduction from GapSVP_2, so it suffices to prove the main theorem for p = 2.The paper notes that the argument can also be adapted directly for 1 < p < ∞.
- Starting hardness: The proof starts from Khot’s SVP variant, whose NO instances satisfy one of three structural conditions involving nonzero coordinates, even coordinates, or Euclidean norm.These properties are designed to remain useful under tensorization.
- Tensor amplification: Tensor products amplify the hardness gap: YES instances retain short vectors, while every nonzero vector in a tensorized NO instance has norm at least d^k/2.The central lemma establishes that the NO-instance structure tensors nicely.
- Tensor amplification: The NO-instance analysis reduces arbitrary tensor vectors to sublattices and handles three structural cases using row support, parity, and a determinant-based matrix inequality.The key inequality relates the trace and determinant of a symmetric positive semidefinite matrix and is combined with Minkowski’s First Theorem.
4 Proof of Theorem 3.3
Theorem 3.3 is proved through a three-step randomized construction: reduce Exact Set Cover to CVP, encode the resulting structure using BCH codes, and restrict to a random sublattice. The construction creates many short vectors in YES instances but few structurally problematic vectors in NO instances.
- Step 1: Exact Set Cover to CVP: The reduction first maps a gap variant of Exact Set Cover to CVP using a lattice kernel and target vector.YES instances yield a lattice vector close to the target, whereas NO instances force every relevant shifted vector to have at least d nonzero coordinates.
- Step 2: BCH-code lattice: The BCH-code lattice ensures that every nonzero vector either has at least d nonzero coordinates or has only even coordinates.A randomized choice of s also guarantees many lattice vectors whose difference from s is a {0,1} vector with exactly r ones.
- Step 2: BCH-code lattice: The intermediate basis Bint combines 2·BCVP, the BCH basis, and a column formed from the CVP target and BCH offset.Its parameters include η = 1/128, r = (3/4+η)d, N = d^2/η, and h = (d/2)log_2 N.
- YES instances: In YES instances, L(Bint) contains at least 1/100·2^h·(N choose r) good lattice vectors with controlled coordinates and short ℓ2 norm.These vectors are formed from compatible CVP and BCH choices and have norm √(4ηd+r) = γ·√d.