Finding shortest lattice vectors faster using quantum search

T.M.M. Laarhoven, Michele Mosca, Joop Pol, van de

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

36 Citaten (Scopus)
134 Downloads (Pure)

Samenvatting

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 2^1.799n+o(n) , improving upon the classical time complexities of 2^2.465n+o(n) of Pujol and Stehlé and the 2^2n+o(n) of Micciancio and Voulgaris, while heuristically we expect to find a shortest vector in time 2^0.268n+o(n) , improving upon the classical time complexity of 2^0.298n+o(n) 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. Keywords: Lattices Shortest vector problem Sieving Quantum search
Originele taal-2Engels
Pagina's (van-tot)375-400
TijdschriftDesigns, Codes and Cryptography
Volume77
Nummer van het tijdschrift2
DOI's
StatusGepubliceerd - 2015

Vingerafdruk Duik in de onderzoeksthema's van 'Finding shortest lattice vectors faster using quantum search'. Samen vormen ze een unieke vingerafdruk.

Citeer dit