CVP / Heuristic · preprocessing query cost

Sieving for closest lattice vectors (with preprocessing)

Thijs Laarhoven

SAC 2016

PublishedSource checked

Time bound: 2^{0.136 n + o(n)}
Space bound: 2^{0.636 n + o(n)}

Source / version date: 16 Jul 2016
Comparison variant: Heuristic · preprocessing query cost
Cost scale: 2^{c n + o(n)}
Computation model: Classical; Gaussian and spherical-list heuristics
Preprocessing cost: 2^{0.636 n + o(n)}

Assumptions and source notes

Heuristic query-time point; preprocessing is excluded from the query cost.

Source location

Abstract; non-adaptive sieving tradeoff
Version: 2016-07-16

Primary source ↗

BibTeXDownload .bib

@inproceedings{laarhoven-cvp-2016,
  author = {Thijs Laarhoven},
  title = {{Sieving for closest lattice vectors (with preprocessing)}},
  booktitle = {Selected Areas in Cryptography (SAC 2016)},
  year = {2016},
  url = {https://arxiv.org/abs/1607.04789},
  keywords = {CVP, CVPP, BDD, sieving},
  cr_date = {2016-07-16},
  cr_status = {published},
  cr_venue = {Selected Areas in Cryptography (SAC 2016)},
  cr_author_ids = {thijs-laarhoven}
}