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
-
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},
url = {https://eprint.iacr.org/2011/139}
}