Finding shortest lattice vectors faster using quantum search

Thijs  Laarhoven; Michele Mosca; Joop Van De Pol

doi:10.1007/s10623-015-0067-5

Finding shortest lattice vectors faster using quantum search

Thijs Laarhoven, Michele Mosca, Joop Van De Pol

Research output: Contribution to journal › Article (Academic Journal) › peer-review

68 Citations (Scopus)

348 Downloads (Pure)

Abstract

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 21.799n+o(n), improving upon the classical time complexities of 22.465n+o(n) of Pujol and Stehlé and the 22n+o(n) of Micciancio and Voulgaris, while heuristically we expect to find a shortest vector in time 20.268n+o(n), improving upon the classical time complexity of 20.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.

Original language	English
Pages (from-to)	375-400
Number of pages	26
Journal	Designs, Codes and Cryptography
Volume	77
Issue number	2
Early online date	14 Apr 2015
DOIs	https://doi.org/10.1007/s10623-015-0067-5
Publication status	Published - Dec 2015

Access to Document

10.1007/s10623-015-0067-5Licence: Unspecified

art%3A10.1007%2Fs10623-015-0067-5
This is the final published version of the article (version of record). It first appeared online via Springer at http://link.springer.com/article/10.1007/s10623-015-0067-5. Please refer to any applicable terms of use of the publisher.
Final published version, 641 KBLicence: CC BY

Handle.net

Persistent link

COED - Computing on Encrypted Data
Smart, N. P. (Principal Investigator)
1/10/11 → 30/09/15
Project: Research

Cite this

@article{95cda3e1ee184706bd1f275dee9330e7,

title = "Finding shortest lattice vectors faster using quantum search",

abstract = "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 21.799n+o(n), improving upon the classical time complexities of 22.465n+o(n) of Pujol and Stehl{\'e} and the 22n+o(n) of Micciancio and Voulgaris, while heuristically we expect to find a shortest vector in time 20.268n+o(n), improving upon the classical time complexity of 20.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.",

author = "Thijs Laarhoven and Michele Mosca and {Van De Pol}, Joop",

year = "2015",

month = dec,

doi = "10.1007/s10623-015-0067-5",

language = "English",

volume = "77",

pages = "375--400",

journal = "Designs, Codes and Cryptography",

issn = "0925-1022",

publisher = "Springer US",

number = "2",

}

TY - JOUR

T1 - Finding shortest lattice vectors faster using quantum search

AU - Laarhoven, Thijs

AU - Mosca, Michele

AU - Van De Pol, Joop

PY - 2015/12

Y1 - 2015/12

N2 - 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 21.799n+o(n), improving upon the classical time complexities of 22.465n+o(n) of Pujol and Stehlé and the 22n+o(n) of Micciancio and Voulgaris, while heuristically we expect to find a shortest vector in time 20.268n+o(n), improving upon the classical time complexity of 20.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.

AB - 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 21.799n+o(n), improving upon the classical time complexities of 22.465n+o(n) of Pujol and Stehlé and the 22n+o(n) of Micciancio and Voulgaris, while heuristically we expect to find a shortest vector in time 20.268n+o(n), improving upon the classical time complexity of 20.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.

U2 - 10.1007/s10623-015-0067-5

DO - 10.1007/s10623-015-0067-5

M3 - Article (Academic Journal)

C2 - 32226228

SN - 0925-1022

VL - 77

SP - 375

EP - 400

JO - Designs, Codes and Cryptography

JF - Designs, Codes and Cryptography

IS - 2

ER -

Finding shortest lattice vectors faster using quantum search

Abstract

Access to Document

Handle.net

Fingerprint

Projects

COED - Computing on Encrypted Data

Cite this