Shortest Vector Problem (SVP)

The shortest vector problem (SVP) asks to find a nonzero vector in a lattice. The problem can be defined with respect to any norm, but the Euclidean norm is the most common. In the approximation version of SVP, the goal is to find a nonzero lattice vector of length at most g times the length of the optimal solution, where the approximation factor g is usually a function of the lattice dimension.

Exact Algorithms

There are three main approaches to the exact solution of SVP in n-dimensional lattices:

Approximation Algorithms

Approximation algorithms for SVP are based on basis reduction techniques, and achieve approximation factors as small as 2O(nloglogn/logn)2^{O(n \log\log n/\log n)} in polynomial time.

Complexity

Approximating SVP in the Euclidean norm is NP-hard (under randomized reductions) for any constant approximation factor O(1)O(1)

  1. Hardness of Approximating the Shortest Vector Problem in Lattices (Khot, J. ACM 52(5):1129-1146, 2005)

Stronger results are known in the \ell_\infty norm, where SVP in is known to be NP-hard under deterministic reductions for quasi polynomial approximation factors 2O(logn/loglogn)=no(1)2^{O(\log n / \log \log n)} = n^{o(1)}.

  1. Approximating SVPinfty to within almost-polynomial factors is NP-hard (Dinur, Theor. Comp. Sci. 285:55-71, 2002).

Approximate SVP is in coNP for O(n)O(\sqrt{n}) factors, and in coAM for O(n/logn)O(\sqrt{n/\log n}) factors. So, it is not NP-hard for such factors, under standard complexity assumptions.

  1. Lattice problems in NP intersect coNP (Aharonov & Regev, J. ACM 52:749-765, 2005)

  2. On the limits of nonapproximability of lattice problems (Goldreich & Goldwasser, J. Comp. Sys. Sci., 60:540-563, 2000)

Open Problems

  1. Inapproximability of the Shortest Vector Problem: Toward a deterministic reduction (Micciancio, Theory of Computing 8(22):487-512, 2012)