Paper 2015/461

Approximate Algorithms on Lattices with Small Determinant

Jung Hee Cheon and Changmin Lee

Abstract

In this paper, we propose approximate lattice algorithms for solving the shortest vector problem (SVP) and the closest vector problem (CVP) on an $n$-dimensional Euclidean integral lattice L. Our algorithms run in polynomial time of the dimension and determinant of lattices and improve on the LLL algorithm when the determinant of a lattice is less than 2^{n^2/4}. More precisely, our approximate SVP algorithm gives a lattice vector of size \le 2^{\sqrt{\log\det L}} and our approximate CVP algorithm gives a lattice vector, the distance of which to a target vector is 2^{\sqrt{\log\det L}} times the distance from the target vector to the lattice. One interesting feature of our algorithms is that their output sizes are independent of dimension and become smaller as the determinant of L becomes smaller. For example, if \det L=2^{n \sqrt n}, a short vector outputted from our approximate SVP algorithm is of size 2^{n^{3/4}}, which is asymptotically smaller than the size 2^{n/4+\sqrt n} of the outputted short vectors of the LLL algorithm. It is similar to our approximate CVP algorithm.