**Shortest Lattice Vectors in the Presence of Gaps**

*Mingjie Liu and Xiaoyun Wang and 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.

**Category / Keywords: **lattice, successive minima, approximate SVP, gap, LWE problem

**Date: **received 21 Mar 2011, last revised 19 Sep 2013

**Contact author: **liumj9705 at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20130919:085325 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]