Improved Algorithms for the Approximate k-List Problem in Euclidean Norm
PKC 2017
PublishedSource checked
- Time bound
- 20.3717 n + o(n)
- Space bound
- 20.1887 n + o(n)
- Source / version date
- 26 Jan 2017
- Comparison variant
- Heuristic · triple sieving
- Cost scale
- 2c n + o(n)
- Computation model
- Classical; heuristic spherical lists
- Preprocessing cost
- Included
- Source locator
- Abstract; Section 7.2, p. 21
Assumptions and source notes
Configuration extension retains the triple-list space exponent.
Source location
Abstract; Section 7.2, p. 21
Version: ePrint 2017/017 revised 26 January 2017
Selected earlier references
Selected sources cited by this paper.
- Tuple lattice sieving
Shi Bai · Thijs Laarhoven · Damien Stehlé · 2016
Improves tuple search and proves earlier configuration/list-size conjectures. Introduction; reference [4]
BibTeXDownload .bib
@inproceedings{herold-kirshanova-2017,
author = {Gottfried Herold and Elena Kirshanova},
title = {{Improved Algorithms for the Approximate k-List Problem in Euclidean Norm}},
booktitle = {Public-Key Cryptography – PKC 2017},
year = {2017},
doi = {10.1007/978-3-662-54365-8_2},
url = {https://eprint.iacr.org/2017/017},
keywords = {SVP, lattice sieving},
cr_date = {2017-01-11},
cr_status = {published},
cr_venue = {Public-Key Cryptography – PKC 2017},
cr_author_ids = {gottfried-herold; elena-kirshanova}
}