TR99-002 Authors: Oded Goldreich, Daniele Micciancio, Shmuel Safra and Jean-Pierre Seifert.

Publication: 22nd January 1999 13:07

Downloads: 2037

Keywords:

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 ${v} \in {L}$

such that $\|v - w\| \leq f(n)\cdot\|u - w\|$ for any ${u} \in {L}$.

Then, our algorithm, on input a lattice ${L}$, outputs a nonzero

vector ${v} \in {L}$ such that $\|{v}\| \leq f(n)\cdot\|{u}\|$ for

any nonzero vector ${u} \in {L}$.

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.