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]...

Descripción completa

Detalles Bibliográficos
Autores principales: Laarhoven, Thijs, Mosca, Michele, van de Pol, Joop
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