**Authors:**
Yi-Kai Liu,
Vadim Lyubashevsky,
Daniele Micciancio

International Workshop on Randomization and Computation - RANDOM 2006, Barcellona, Spain. Springer LNCS 4110, pp. 450-461 (August 2006)

DOI:10.1007/11830924_41

[BibTeX]
[Postscript]
[PDF]

**Abstract:**
We show how a recent technique developed by
(Aharonov and Regev, JACM 2005) can be used to find the closest lattice
vector when the target point is not too far from the lattice. We prove that
for any lattice *L*, given a polynomial size advice string, there is a
polynomial time algorithm that can find the closest vector in the lattice for
every target point that is within *sqrt{ log(n) / n } lambda(L)* of
the lattice (where *lambda(L)* is the length of the shortest vector of
*L*). This improves on the previously best known algorithm for this
problem (Klein, SODA 2000), which runs in polynomial time when the target
point is within *O(lambda(L)/n)* and a "good" basis for the lattice
known.