On bounded distance decoding for general lattices

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)

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