SVP / Classical · heuristic

Tuple lattice sieving

Shi Bai · Thijs Laarhoven · Damien Stehlé

LMS Journal of Computation and Mathematics 2016

PublishedSource checked

Time bound: 2^{0.4812 n + o(n)}
Space bound: 2^{0.1887 n + o(n)}

Source / version date: 21 Jul 2016
Comparison variant: Classical · heuristic
Cost scale: 2^{c n + o(n)}
Computation model: Classical; heuristic spherical lists
preprocessing: Included in asymptotic analysis
reference: Abstract; Section 4

Assumptions and source notes

Introduces tuple sieving to reduce the sieve-list memory. The representative filtered triple-sieve point is included in the unrestricted heuristic SVP literature even though it does not improve the standing time exponent. Pair filtering before the third-vector search.

Source location

Abstract; Section 4
Version: ePrint 2016/713; first received 21 July 2016; published text August 2016

Selected earlier references

Selected sources cited by this paper.

Sieve Algorithms for the Shortest Vector Problem are Practical
Phong Q. Nguyen · Thomas Vidick · 2008
Extends pairwise sieving to tuples. Introduction and Section 3; reference [22]
New directions in nearest neighbor searching with applications to lattice sieving
Anja Becker · Léo Ducas · Nicolas Gama · Thijs Laarhoven · 2016
Uses the earlier pair-sieving time and memory baseline. Introduction; reference [5]

Primary source ↗

BibTeXDownload .bib

@article{bai-laarhoven-stehle-2016,
  author = {Shi Bai and Thijs Laarhoven and Damien Stehlé},
  title = {{Tuple lattice sieving}},
  journal = {LMS Journal of Computation and Mathematics},
  year = {2016},
  doi = {10.1112/S1461157016000292},
  url = {https://eprint.iacr.org/2016/713},
  keywords = {SVP, lattice sieving},
  cr_date = {2016-07-21},
  cr_status = {published},
  cr_venue = {LMS Journal of Computation and Mathematics},
  cr_author_ids = {shi-bai; thijs-laarhoven; damien-stehle}
}