Paper Info
Title
A Three-Level Sieve Algorithm for the Shortest Vector Problem.
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.
Year
DOI
Venue
2013
10.1007/978-3-662-43414-7_2
Lecture Notes in Computer Science
Keywords
DocType
Volume
Lattice,Shortest vector problem,Sieve algorithm,Sphere covering
Conference
8282
ISSN
Citations 
PageRank 
0302-9743
18
0.70
References 
Authors
19
3
Name
Order
Citations
PageRank
Feng Zhang122825.71
Yanbin Pan23513.29
Gengran Hu3203.11