Cryptology ePrint Archive: Report 2011/139

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 4 Mar 2012

Contact author: xiaoyunwang at mail tsinghua edu cn,liu-mj07@mails tsinghua edu cn,

Available formats: PDF | BibTeX Citation

Version: 20120304:125035 (All versions of this report)

Discussion forum: Show discussion | Start new discussion