All reports by Author Shmuel Safra and
Jean-Pierre Seifert.:

__
TR99-002
| 22nd January 1999
__

Oded Goldreich, Daniele Micciancio, Shmuel Safra and Jean-Pierre Seifert.#### Approximating shortest lattice vectors is not harder than approximating closest lattice vectors.

Oded Goldreich, Daniele Micciancio, Shmuel Safra and Jean-Pierre Seifert.

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 ...
more >>>