Shortest vector problem in L₂ is NP-hard for randomized reductions

Abstract

We show that the shortest vector problem in lattices with L2. norm is NP-hard for randomized reductions. Moreover we also show that there is an absolute constant ε>0 so that to find a vector which is longer than the shortest non-zero vector by no more than a factor of 1+2-n(ε) (with respect to the L2 norm) is also NP-hard for randomized reductions. The corresponding decision problem is NP-complete for randomized reductions.