A Three-Level Sieve Algorithm for the   Shortest Vector Problem

Feng Zhang; Yanbin Pan; Gengran Hu

Paper 2013/536

A Three-Level Sieve Algorithm for the Shortest Vector Problem

Feng Zhang, 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.

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.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Minor revision. SAC 2013
DOI: 10.1007/978-3-662-43414-7_2
Keywords: Lattice Shortest Vector Problem Sieve Algorithm Sphere Covering
Contact author(s): panyanbin @ amss ac cn
History: 2014-10-22: revised; 2013-08-30: received; See all versions
Short URL: https://ia.cr/2013/536
License: CC BY

BibTeX

@misc{cryptoeprint:2013/536,
      author = {Feng Zhang and Yanbin Pan and Gengran Hu},
      title = {A Three-Level Sieve Algorithm for the   Shortest Vector Problem},
      howpublished = {Cryptology {ePrint} Archive, Paper 2013/536},
      year = {2013},
      doi = {10.1007/978-3-662-43414-7_2},
      url = {https://eprint.iacr.org/2013/536}
}