Finding shortest lattice vectors faster using quantum search
Designs, Codes and Cryptography 2015
- Time bound
- 20.286 n + o(n)
- Space bound
- —
- Source / version date
- 4 Nov 2014
- Comparison variant
- Quantum · heuristic
- Cost scale
- 2c n + o(n)
- QRAM / random access
- Quantum-addressable classical lists
- Quantum memory
- Consult source version
- Operation model
- Sequential quantum search with angular LSH
Assumptions and source notes
Earlier preprint abstract states .286. Space for that original version was not independently recovered.
Source location
Abstract and archive history (2014-11-04 received); later journal Theorem 3
Version: ePrint 2014/907 abstract; received 4 November 2014
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]
@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}
}