Cargando…
Finding shortest lattice vectors faster using quantum search
By applying a quantum search algorithm to various heuristic and provable sieve algorithms from the literature, we obtain improved asymptotic quantum results for solving the shortest vector problem on lattices. With quantum computers we can provably find a shortest vector in time [Formula: see text]...
Autores principales: | , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
Springer US
2015
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7089694/ https://www.ncbi.nlm.nih.gov/pubmed/32226228 http://dx.doi.org/10.1007/s10623-015-0067-5 |
_version_ | 1783509785518276608 |
---|---|
author | Laarhoven, Thijs Mosca, Michele van de Pol, Joop |
author_facet | Laarhoven, Thijs Mosca, Michele van de Pol, Joop |
author_sort | Laarhoven, Thijs |
collection | PubMed |
description | By applying a quantum search algorithm to various heuristic and provable sieve algorithms from the literature, we obtain improved asymptotic quantum results for solving the shortest vector problem on lattices. With quantum computers we can provably find a shortest vector in time [Formula: see text] , improving upon the classical time complexities of [Formula: see text] of Pujol and Stehlé and the [Formula: see text] of Micciancio and Voulgaris, while heuristically we expect to find a shortest vector in time [Formula: see text] , improving upon the classical time complexity of [Formula: see text] of Laarhoven and De Weger. These quantum complexities will be an important guide for the selection of parameters for post-quantum cryptosystems based on the hardness of the shortest vector problem. |
format | Online Article Text |
id | pubmed-7089694 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2015 |
publisher | Springer US |
record_format | MEDLINE/PubMed |
spelling | pubmed-70896942020-03-26 Finding shortest lattice vectors faster using quantum search Laarhoven, Thijs Mosca, Michele van de Pol, Joop Des Codes Cryptogr Article By applying a quantum search algorithm to various heuristic and provable sieve algorithms from the literature, we obtain improved asymptotic quantum results for solving the shortest vector problem on lattices. With quantum computers we can provably find a shortest vector in time [Formula: see text] , improving upon the classical time complexities of [Formula: see text] of Pujol and Stehlé and the [Formula: see text] of Micciancio and Voulgaris, while heuristically we expect to find a shortest vector in time [Formula: see text] , improving upon the classical time complexity of [Formula: see text] of Laarhoven and De Weger. These quantum complexities will be an important guide for the selection of parameters for post-quantum cryptosystems based on the hardness of the shortest vector problem. Springer US 2015-04-14 2015 /pmc/articles/PMC7089694/ /pubmed/32226228 http://dx.doi.org/10.1007/s10623-015-0067-5 Text en © The Author(s) 2015 Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. |
spellingShingle | Article Laarhoven, Thijs Mosca, Michele van de Pol, Joop Finding shortest lattice vectors faster using quantum search |
title | Finding shortest lattice vectors faster using quantum search |
title_full | Finding shortest lattice vectors faster using quantum search |
title_fullStr | Finding shortest lattice vectors faster using quantum search |
title_full_unstemmed | Finding shortest lattice vectors faster using quantum search |
title_short | Finding shortest lattice vectors faster using quantum search |
title_sort | finding shortest lattice vectors faster using quantum search |
topic | Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7089694/ https://www.ncbi.nlm.nih.gov/pubmed/32226228 http://dx.doi.org/10.1007/s10623-015-0067-5 |
work_keys_str_mv | AT laarhoventhijs findingshortestlatticevectorsfasterusingquantumsearch AT moscamichele findingshortestlatticevectorsfasterusingquantumsearch AT vandepoljoop findingshortestlatticevectorsfasterusingquantumsearch |