SVP / Heuristic · triple sieving

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

Gottfried Herold · Elena Kirshanova · Thijs Laarhoven

PKC 2018

PublishedSource checked

Time bound: 2^{0.33 n + o(n)}
Space bound: 2^{0.2075 n + o(n)}

Source / version date: 22 Dec 2017
Comparison variant: Heuristic · triple sieving
Cost scale: 2^{c n + o(n)}
Computation model: Classical; heuristic tuple sieving

Assumptions and source notes

A triple-sieving time–memory tradeoff point from the abstract.

Source location

Abstract
Version: 2017-12-22

Selected earlier references

Selected sources cited by this paper.

Improved Algorithms for the Approximate k-List Problem in Euclidean Norm
Gottfried Herold · Elena Kirshanova · 2017
Extends configuration search and its time-memory tradeoffs. Abstract and Section 1; reference [HK17]
Tuple lattice sieving
Shi Bai · Thijs Laarhoven · Damien Stehlé · 2016
Improves earlier tuple-sieving bounds. Abstract and Section 1; reference [BLS16]

Primary source ↗

BibTeXDownload .bib

@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}
}