CVP / Heuristic · classical

Sieving for closest lattice vectors (with preprocessing)

Thijs Laarhoven

SAC 2016

PublishedSource checked

Time bound: (3/2)^{n/2 + o(n)}
Space bound: (4/3)^{n/2 + o(n)}

Source / version date: 16 Jul 2016
Comparison variant: Heuristic · classical
Cost scale: 2^{c n + o(n)}
Computation model: Classical; Heuristic 2

Assumptions and source notes

Theorem 1, assuming Heuristic 2.

Source location

Theorem 1, p.6
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}
}