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
LatticeShortest Vector ProblemSieve AlgorithmSphere 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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2013/536}},
      url = {https://eprint.iacr.org/2013/536}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.