Shortest Lattice Vectors in the Presence of Gaps.
Mingjie Liu, Xiaoyun Wang, Guangwu Xu, Xuexin Zheng · 2011
Given a lattice L with the i-th successive minimum λi, its i-th gap λi often provides useful λ1 information for analyzing the security of cryptographic scheme related to L. This paper concerns short vectors for lattices with gaps. In the first part, a λ2-gap estimation of LWE lattices with cryptographic significance is given. For some γ ′ , a better reduction from BDDγ ′ to uSV Pγ is obtained in the presence of larger λ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.