On the hardness of the shortest vector problem
Daniele Micciancio, Shafi Goldwasser · 1998
A lattice is the set of intersection points of an infinite n-dimensional grid. One of the most fundamental algorithmic problems on lattices is the shortest vector problem (SVP): given a lattice, find the shortest non-zero vector in it (i.e., the intersection points closest to the origin). We prove that the shortest vector problem is NP-hard (for randomized reductions) to approximate within some constant factor greater than 1 in any l p norm (p 1). In particular, we prove the NP-hardness of approximating SVP in the Euclidean norm l 2 within any factor less than 2. The same NP-hardness results hold for deterministic non-uniform reductions. A deterministic uniform reduction is also given under a reasonable number theoretic conjecture concerning the distribution of smooth numbers. In proving