Speed-ups and time-memory trade-offs for tuple lattice sieving

Gottfried Herold · Elena Kirshanova · Thijs Laarhoven

PKC 2018

Time bound

2^{0.3588 n + o(n)}

Space bound

2^{0.1887 n + o(n)}

Source / version date

22 Dec 2017

Comparison variant

Classical · heuristic

Cost scale

2^{c n + o(n)}

Computation model

Classical; heuristic tuple sieving

Assumptions and source notes

Combines configuration search with spherical locality-sensitive filtering. This representative low-memory point advances tuple sieving but is slower than the unrestricted pair-sieving time record. A triple-sieving time–memory tradeoff point from the abstract.

Source location

Abstract
Version: 2017-12-22

Primary source ↗

@inproceedings{herold-kirshanova-laarhoven-2017,
  author = {Gottfried Herold and Elena Kirshanova and Thijs Laarhoven},
  title = {{Speed-ups and time-memory trade-offs for tuple lattice sieving}},
  booktitle = {PKC 2018},
  year = {2018},
  url = {https://eprint.iacr.org/2017/1228},
  keywords = {SVP, tuple sieving, time-memory tradeoffs},
  cr_date = {2017-12-22},
  cr_status = {published},
  cr_venue = {PKC 2018},
  cr_author_ids = {gottfried-herold; elena-kirshanova; thijs-laarhoven}
}