Given a lattice L and a target vector t in Euclidean space, the Closest Vector Problem (CVP) asks for the point in L closest to t. The pre-processing version of the problem (denoted by CVPP) allows arbitrary processing on the lattice L but must run in polynomial time once the target vector t is revealed.

The complexity of solving CVPP exactly and approximately is important from a cryptographic point of view. The best known approximation for CVP is only slightly better than 2^n while for CVPP Ahoronov and Regev gave an algorithm achieving approximation factor \sqrt{n}. However the previous best hardness result for this problem was poly-logarithmic.

We show that unless NP is contained in quasi-polynomial time, the problem is hard to approximate to factor 2^{(\log n)^C} where C can be a constant arbitrary close to 1.

Joint work with Subhash Khot and Nisheeth Vishnoi.