Next: Improved Testing Algorithms for
Up: Back at Weizmann (1998-2003)
Previous: Back at Weizmann (1998-2003)
This work presents a Cook-reduction of the problem
of approximating the shortest vector in a lattice
to the problem of approximating the closest vectors in a lattice.
The reduction is simple, preserves the level of approximation
as well as the dimension of the lattice, and works both for the
search and decision versions.
Comments:
Authored by O. Goldreich, D. Micciancio, S. Safra and J.P. Seifert. Appeared in
- IPL, 71, pages 55-61, 1999.
Oded Goldreich
2003-07-30