Paper 2011/139 Original: eprint.iacr.org/2011/139 ↗
Shortest Lattice Vectors in the Presence of Gaps
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
- Preprint.
- History
- 2013-09-19: last updated
- 2011-03-22: published
- Short URL
- https://ia.cr/2011/139
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}