Approximating shortest lattice vectors is not harder than approximating closest lattice

摘要

We show that given oracle access to a subroutine which returns approximate closest vectors in a lattice, one may find in polynomial-time approximate shortest vectors in a lattice. The level of approximation is maintained; that is, for any function f, the following holds: Suppose that the subroutine, on input a lattice L and a target vector w (not necessarily in the lattice), outputs vL such that v?wf(n)u?w for any uL. Then, our algorithm, on input a lattice L, outputs a nonzero vector vL such that vf(n)u for any nonzero vector uL. The result holds for any norm, and preserves the dimension of the lattice, i.e., the closest vector oracle is called on lattices of exactly the same dimension as the original shortest vector problem. This result establishes the widely believed conjecture by which the shortest vector problem is not harder than the closest vector problem. The proof can be easily adapted to establish an analogous result for the corresponding computational problems for linear codes.