You are looking at a specific version 20130830:092922 of this paper.
See the latest version.
Paper 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 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.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. Lecture Notes in Computer Science
- Keywords
- LatticeShortest Vector ProblemSieve AlgorithmSphere Covering
- Contact author(s)
-
zhangfeng @ amss ac cn
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