Solving the shortest vector problem in lattices faster using quantum search

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

doi:10.1007/978-3-642-38616-9_6

Solving the shortest vector problem in lattices faster using quantum search

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

Discrete Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

21 Citations (Scopus)

Abstract

By applying Grover’s quantum search algorithm to the lattice algorithms of Micciancio and Voulgaris, Nguyen and Vidick, Wang et al., and Pujol and Stehlé, we obtain improved asymptotic quantum results for solving the shortest vector problem. With quantum computers we can provably find a shortest vector in time 21.799n + o(n), improving upon the classical time complexity 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.312n + o(n), improving upon the classical time complexity of 20.384n + o(n) of Wang et al. 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
Title of host publication	Post-Quantum Cryptography - 5th International Workshop (PQ Crypto 2013, Limoges, France, June 4-7, 2013. Proceedings)
Editors	Ph. Gaborit
Place of Publication	Berlin
Publisher	Springer
Pages	83-101
Number of pages	19
ISBN (Print)	978-3-642-38615-2
DOIs	https://doi.org/10.1007/978-3-642-38616-9_6
Publication status	Published - 2013
Event	5th International Conference on Post-Quantum Cryptography (PQCrypto 2013) - Limoges, France Duration: 4 Jun 2013 → 7 Jun 2013 Conference number: 5 http://pqcrypto2013.xlim.fr/

Publication series

Name	Lecture Notes in Computer Science
Volume	7932
ISSN (Print)	0302-9743

Conference

Conference	5th International Conference on Post-Quantum Cryptography (PQCrypto 2013)
Abbreviated title	PQCrypto 2013
Country/Territory	France
City	Limoges
Period	4/06/13 → 7/06/13
Internet address	http://pqcrypto2013.xlim.fr/

Access to Document

10.1007/978-3-642-38616-9_6

21 Citations - based on content available in repository [source: Scopus]
1 Report
1 Phd Thesis 1 (Research TU/e / Graduation TU/e)

Search problems in cryptography: from fingerprinting to lattice sieving
Laarhoven, T., 16 Feb 2016, Eindhoven: Technische Universiteit Eindhoven. 219 p.
Research output: Thesis › Phd Thesis 1 (Research TU/e / Graduation TU/e)

Open Access
File
Solving the shortest vector problem in lattices faster using quantum search
Laarhoven, T. M. M., Mosca, M. & Pol, van de, J., 2013, s.n. 19 p. (arXiv.org; vol. 1301.6176 [cs.CR])
Research output: Book/Report › Report › Academic

Cite this

Laarhoven, T. M. M., Mosca, M., & van de Pol, J. (2013). Solving the shortest vector problem in lattices faster using quantum search. In P. Gaborit (Ed.), Post-Quantum Cryptography - 5th International Workshop (PQ Crypto 2013, Limoges, France, June 4-7, 2013. Proceedings) (pp. 83-101). (Lecture Notes in Computer Science; Vol. 7932). Springer. https://doi.org/10.1007/978-3-642-38616-9_6

@inproceedings{88ab488618404ad9ac543a37331392dc,

title = "Solving the shortest vector problem in lattices faster using quantum search",

abstract = "By applying Grover{\textquoteright}s quantum search algorithm to the lattice algorithms of Micciancio and Voulgaris, Nguyen and Vidick, Wang et al., and Pujol and Stehl{\'e}, we obtain improved asymptotic quantum results for solving the shortest vector problem. With quantum computers we can provably find a shortest vector in time 21.799n + o(n), improving upon the classical time complexity 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.312n + o(n), improving upon the classical time complexity of 20.384n + o(n) of Wang et al. 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 = "T.M.M. Laarhoven and Michele Mosca and {van de Pol}, Joop",

year = "2013",

doi = "10.1007/978-3-642-38616-9_6",

language = "English",

isbn = "978-3-642-38615-2",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "83--101",

editor = "Ph. Gaborit",

booktitle = "Post-Quantum Cryptography - 5th International Workshop (PQ Crypto 2013, Limoges, France, June 4-7, 2013. Proceedings)",

address = "Germany",

note = "5th International Conference on Post-Quantum Cryptography (PQCrypto 2013), PQCrypto 2013 ; Conference date: 04-06-2013 Through 07-06-2013",

url = "http://pqcrypto2013.xlim.fr/",

}

Laarhoven, TMM, Mosca, M & van de Pol, J 2013, Solving the shortest vector problem in lattices faster using quantum search. in P Gaborit (ed.), Post-Quantum Cryptography - 5th International Workshop (PQ Crypto 2013, Limoges, France, June 4-7, 2013. Proceedings). Lecture Notes in Computer Science, vol. 7932, Springer, Berlin, pp. 83-101, 5th International Conference on Post-Quantum Cryptography (PQCrypto 2013), Limoges, France, 4/06/13. https://doi.org/10.1007/978-3-642-38616-9_6

Solving the shortest vector problem in lattices faster using quantum search. / Laarhoven, T.M.M.; Mosca, Michele; van de Pol, Joop.
Post-Quantum Cryptography - 5th International Workshop (PQ Crypto 2013, Limoges, France, June 4-7, 2013. Proceedings). ed. / Ph. Gaborit. Berlin: Springer, 2013. p. 83-101 (Lecture Notes in Computer Science; Vol. 7932).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Solving the shortest vector problem in lattices faster using quantum search

AU - Laarhoven, T.M.M.

AU - Mosca, Michele

AU - van de Pol, Joop

N1 - Conference code: 5

PY - 2013

Y1 - 2013

N2 - By applying Grover’s quantum search algorithm to the lattice algorithms of Micciancio and Voulgaris, Nguyen and Vidick, Wang et al., and Pujol and Stehlé, we obtain improved asymptotic quantum results for solving the shortest vector problem. With quantum computers we can provably find a shortest vector in time 21.799n + o(n), improving upon the classical time complexity 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.312n + o(n), improving upon the classical time complexity of 20.384n + o(n) of Wang et al. 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 Grover’s quantum search algorithm to the lattice algorithms of Micciancio and Voulgaris, Nguyen and Vidick, Wang et al., and Pujol and Stehlé, we obtain improved asymptotic quantum results for solving the shortest vector problem. With quantum computers we can provably find a shortest vector in time 21.799n + o(n), improving upon the classical time complexity 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.312n + o(n), improving upon the classical time complexity of 20.384n + o(n) of Wang et al. 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/978-3-642-38616-9_6

DO - 10.1007/978-3-642-38616-9_6

M3 - Conference contribution

SN - 978-3-642-38615-2

T3 - Lecture Notes in Computer Science

SP - 83

EP - 101

BT - Post-Quantum Cryptography - 5th International Workshop (PQ Crypto 2013, Limoges, France, June 4-7, 2013. Proceedings)

A2 - Gaborit, Ph.

PB - Springer

CY - Berlin

T2 - 5th International Conference on Post-Quantum Cryptography (PQCrypto 2013)

Y2 - 4 June 2013 through 7 June 2013

ER -

Solving the shortest vector problem in lattices faster using quantum search

Abstract

Publication series

Conference

Access to Document

Fingerprint

Research output

Search problems in cryptography: from fingerprinting to lattice sieving

Solving the shortest vector problem in lattices faster using quantum search

Cite this