



01845nas a2200145   4500008004100000245005400041210005100095260001500146300001200161520139800173100001601571700002401587700002401611856006401635       2006                        eng d00aOn Bounded Distance Decoding for General Lattices0 aBounded Distance Decoding for General Lattices  c2006/01/01  a450-4613 aA central problem in the algorithmic study of lattices is the closest vector problem: given a lattice L represented by some basis, and a target point y⃗ , find the lattice point closest to y⃗ . Bounded Distance Decoding is a variant of this problem in which the target is guaranteed to be close to the lattice, relative to the minimum distance λ1(L) of the lattice. Specifically, in the α-Bounded Distance Decoding problem (α-BDD), we are given a lattice L and a vector y⃗  (within distance α⋅λ1(L) from the lattice), and we are asked to find a lattice point x⃗ ∈L within distance α⋅λ1(L) from the target. In coding theory, the lattice points correspond to codewords, and the target points correspond to lattice points being perturbed by noise vectors. Since in coding theory the lattice is usually fixed, we may “pre-process” it before receiving any targets, to make the subsequent decoding faster. This leads us to consider α-BDD with pre-processing. We show how a recent technique of Aharonov and Regev [2] can be used to solve α-BDD with pre-processing in polynomial time for α=O((logn)/n−−−−−−−√). This improves upon the previously best known algorithm due to Klein [13] which solved the problem for α=O(1/n). We also establish hardness results for α-BDD and α-BDD with pre-processing, as well as generalize our results to other ℓ p norms.1 aLiu, Yi-Kai1 aLyubashevsky, Vadim1 aMicciancio, Daniele  uhttp://link.springer.com/chapter/10.1007/11830924_41#page-1