Finding shortest lattice vectors faster using quantum search
Designs, Codes and Cryptography 2015
PublishedSource checked
- Time bound
- 21.799 n + o(n)
- Space bound
- 21.286 n + o(n)
- Source / version date
- 14 Apr 2015
- Comparison variant
- Quantum · worst case
- Cost scale
- 2c n + o(n)
- Computation model
- Quantum search; coherent classical-list access
- reference
- DCC 77:375–400
Assumptions and source notes
The provable quantum sieving bound in the journal article.
Source location
Abstract; provable sieve analysis
Version: 2015-04-14
Selected earlier references
Selected sources cited by this paper.
- Solving the Shortest Vector Problem in Lattices Faster Using Quantum Search
Thijs Laarhoven · Michele Mosca · Joop van de Pol · 2013
Expanded journal version of the PQCrypto 2013 work. Title-page note; reference [50]
- Sieving for shortest vectors in lattices using angular locality-sensitive hashing
Thijs Laarhoven · 2015
Quantum search applied to angular-LSH sieving. Section 5; reference [47]
- Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing
Thijs Laarhoven · Benne de Weger · 2015
Quantum search applied to spherical-LSH sieving. Section 6; reference [48]
- Solving the Shortest Lattice Vector Problem in Time 2^(2.465n)
Xavier Pujol · Damien Stehlé · 2009
Provable quantum analysis builds on the earlier birthday sieve. Section 2; reference [65]
BibTeXDownload .bib
@article{paper-caa5f6c38871,
author = {Thijs Laarhoven and Michele Mosca and Joop van de Pol},
title = {{Finding shortest lattice vectors faster using quantum search}},
journal = {Designs, Codes and Cryptography},
year = {2015},
volume = {77},
pages = {375--400},
doi = {10.1007/s10623-015-0067-5},
url = {https://doi.org/10.1007/s10623-015-0067-5},
cr_date = {2015-04-14},
cr_status = {published},
cr_venue = {Designs, Codes and Cryptography},
cr_author_ids = {thijs-laarhoven; michele-mosca; joop-van-de-pol}
}