Summary: By applying Grover’s quantum search algorithm to the lattice algorithms of D. Micciancio and P. Voulgaris [SODA 2010, New York, NY: ACM, 1468–1480 (2010; Zbl 1288.94076), P.-Q. Nguyen and J. Vidick [J. Math. Cryptol. 2, No. 2, 181-207 (2008; Zbl 1193.11117)], X. Wang et al. [“Improved Nguyen-Vidick heuristic sieve algorithm for shortest vector problem.” In: 6th ACM Symposium on Information, Computer and Communications Security (ASIACCS), New York, NY: ACM, 1–9 (2011), doi:10.1145/1966913.1966915], and X. Pujol and D. Stehlé [“Solving the shortest lattice vector problem in time \(2^{2.465n}\). Cryptology ePrint Archive, Report 2009/605, 1–7 (2009)], we obtain improved asymptotic quantum results for solving the shortest vector problem. With quantum computers we can provably find a shortest vector in time \(2^{1.799n + o(n)}\), improving upon the classical time complexity 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.312n + o(n)}\), improving upon the classical time complexity of \(2^{0.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.
For the entire collection see [Zbl 1263.94004].