Paper 2011/139

Shortest Lattice Vectors in the Presence of Gaps

Mingjie Liu, Xiaoyun Wang, Guangwu Xu, and Xuexin Zheng

Abstract

Given a lattice ${\mathcal L}$ with the $i$-th successive minimum $\lambda_i$, its $i$-th gap $\frac{\lambda_i}{\lambda_1}$ often provides useful information for analyzing the security of cryptographic scheme related to ${\mathcal L}$. This paper concerns short vectors for lattices with gaps. In the first part, a $\lambda_2$-gap estimation of LWE lattices with cryptographic significance is given. For some $\gamma'$, a better reduction from $BDD_{\gamma'}$ to $uSVP_{\gamma}$ is obtained in the presence of larger $\lambda_2$-gap. The second part of the paper shows that gaps among the successive minima lead to a more efficient SVP search algorithm. As far as we know, it is the first SVP algorithm exploiting lattices with gaps.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown status
Keywords
latticesuccessive minimaapproximate SVPgapLWE problem
Contact author(s)
liumj9705 @ gmail com
History
2013-09-19: last of 5 revisions
2011-03-22: received
See all versions
Short URL
https://ia.cr/2011/139
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/139,
      author = {Mingjie Liu and Xiaoyun Wang and Guangwu Xu and Xuexin Zheng},
      title = {Shortest Lattice Vectors in the Presence of Gaps},
      howpublished = {Cryptology ePrint Archive, Paper 2011/139},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/139}},
      url = {https://eprint.iacr.org/2011/139}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.