We show that the problem of deciding whether a given rational lattice L has a vector of length less than some given value r is NP-hard under randomized reductions, even under the promise that L has exactly zero or one vector of length less than r.
['Ravi Kumar', 'D. Sivakumar']
A note on the shortest lattice vector problem