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 }^{\prime }$, a better reduction from $BD{D}_{{\gamma }^{\prime }}$ to $uSV{P}_{\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.