Cryptology ePrint Archive: Report 2013/536

A Three-Level Sieve Algorithm for the Shortest Vector Problem

Feng Zhang and Yanbin Pan and Gengran Hu

Abstract: In AsiaCCS 2011, Wang \textit{et al.} proposed a two-level heuristic sieve algorithm for the shortest vector problem in lattices, which improves the Nguyen-Vidick sieve algorithm. Inspired by their idea, we present a three-level sieve algorithm in this paper, which is shown to have better time complexity. More precisely, the time complexity of our algorithm is $2^{0.3778n+o(n)}$ polynomial-time operations and the corresponding space complexity is $2^{0.2833n+o(n)}$ polynomially many bits.

Category / Keywords: Lattice, Shortest Vector Problem, Sieve Algorithm, Sphere Covering

Original Publication (with minor differences): SAC 2013
DOI: 10.1007/978-3-662-43414-7_2

Date: received 27 Aug 2013, last revised 22 Oct 2014

Contact author: panyanbin at amss ac cn

Available format(s): PDF | BibTeX Citation

Note: We would like to thank Thijs Laarhoven, who pointed out there was some mistake in the previous version. We correct it in this version.

Version: 20141022:121646 (All versions of this report)

Short URL: ia.cr/2013/536

Discussion forum: Show discussion | Start new discussion