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)
 Publication info
 Preprint. MINOR revision.
 Keywords
 LLL algorithmSVPCVPHermite normal formBabai's nearest plane algorithm
 Contact author(s)
 cocomi11 @ snu ac kr
 History
 20160118: last of 2 revisions
 20150514: received
 See all versions
 Short URL
 https://ia.cr/2015/461
 License

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} }