Paper 2011/139

Shortest Lattice Vectors in the Presence of Gaps

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


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.

Available format(s)
Publication info
Published elsewhere. Unknown status
latticesuccessive minimaapproximate SVPgapLWE problem
Contact author(s)
liumj9705 @ gmail com
2013-09-19: last of 5 revisions
2011-03-22: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.