Theory of Computing
-------------------
Title     : Inapproximability of the Shortest Vector Problem: Toward a Deterministic Reduction
Authors   : Daniele Micciancio
Volume    : 8
Number    : 22
Pages     : 487-512
URL       : https://theoryofcomputing.org/articles/v008a022

Abstract
--------

We prove that the Shortest Vector Problem (SVP) on point lattices is
NP-hard to approximate for any constant factor under polynomial time
randomized reductions with one-sided error that produce no false
positives. We also prove inapproximability for quasi-polynomial
factors under the same kind of reductions running in subexponential
time. Previous hardness results for SVP either incurred two-sided
error, or only proved hardness for small constant approximation
factors. Close similarities between our reduction and recent results
on the complexity of the analogous problem on linear codes make our
new proof an attractive target for derandomization, paving the road to
a possible NP-hardness proof for SVP under deterministic polynomial
time reductions.