Cryptology ePrint Archive: Report 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.

Category / Keywords: LLL algorithm, SVP, CVP, Hermite normal form, Babai's nearest plane algorithm

Date: received 13 May 2015, last revised 17 Jan 2016

Contact author: cocomi11 at snu ac kr

Available format(s): PDF | BibTeX Citation

Version: 20160118:053557 (All versions of this report)

Short URL: ia.cr/2015/461

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]