ECCC-Report TR99-002https://eccc.weizmann.ac.il/report/1999/002Comments and Revisions published for TR99-002en-usFri, 22 Jan 1999 13:07:47 +0200
Paper TR99-002
| Approximating shortest lattice vectors is not harder than approximating closest lattice vectors. |
Oded Goldreich,
Daniele Micciancio,
Shmuel Safra and
Jean-Pierre Seifert.
https://eccc.weizmann.ac.il/report/1999/002We 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.
Fri, 22 Jan 1999 13:07:47 +0200https://eccc.weizmann.ac.il/report/1999/002