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.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
LLL algorithmSVPCVPHermite normal formBabai's nearest plane algorithm
Contact author(s)
cocomi11 @ snu ac kr
History
2016-01-18: last of 2 revisions
2015-05-14: received
See all versions
Short URL
https://ia.cr/2015/461
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/461,
      author = {Jung Hee Cheon and Changmin Lee},
      title = {Approximate Algorithms on Lattices with  Small Determinant},
      howpublished = {Cryptology ePrint Archive, Paper 2015/461},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/461}},
      url = {https://eprint.iacr.org/2015/461}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.