A Three-Level Sieve Algorithm for the Shortest Vector Problem

Feng Zhang · Yanbin Pan · Gengran Hu

SAC 2013

Time bound

2^{0.3778 n + o(n)}

Space bound

2^{0.2833 n + o(n)}

Source / version date

22 Oct 2014

Comparison variant

Classical · heuristic

Cost scale

2^{c n + o(n)}

Norm

Euclidean ℓ₂

Success guarantee

Under the stated sieve heuristic

Computation model

Classical randomized; polynomial factors suppressed

Heuristic assumption

Uniform sieve lists; three-level covering

reference

ZPH13

Assumptions and source notes

SAC 2013. The current source gives 0.3778 time and 0.2833 space. The ePrint explicitly reports a mistake in the previous version, corrected on 22 October 2014; this conservative chronology dates this coefficient to that corrected version, rather than backdating it to the first 30 August 2013 submission.

Primary source ↗

@misc{paper-57677bda59d7,
  author = {Feng Zhang and Yanbin Pan and Gengran Hu},
  title = {{A Three-Level Sieve Algorithm for the Shortest Vector Problem}},
  year = {2014},
  doi = {10.1007/978-3-662-43414-7_2},
  url = {https://eprint.iacr.org/2013/536},
  cr_date = {2014-10-22},
  cr_status = {published},
  cr_venue = {SAC 2013},
  cr_author_ids = {feng-zhang; yanbin-pan; gengran-hu},
  howpublished = {Cryptology {ePrint} Archive, Paper 2013/536}
}