# Approximating shortest lattice vectors is not harder than
approximating closest lattice vectors

**Authors:** Oded Goldreich, Daniele Micciancio,
Shmuel Safra and Jean-Pierre Seifert

Information Processing Letters, **71**(2):55-61
(1999)

[BibTeX] [PostScript] [PDF]
[doi:10.1016/S0020-0190(99)00083-6]

**Abstract:** 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**|| <= *f(n)*
||**u**-**w**|| for any
**u** in *L*. Then, our algorithm, on input a
lattice *L,* outputs a non-zero vector
**v** in *L* such that ||**v**||
<= *f(n)*||**u**|| for any non-zero 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.

## Notes

Preliminary version:
ECCC TR99-002.