On the practicality of quantum sieving algorithms for the shortest vector problem

Joao F. Doriguello; George Giapitzakis; Alessandro Luongo; Aditya Morolia

Paper 2024/1692

On the practicality of quantum sieving algorithms for the shortest vector problem

Joao F. Doriguello

, HUN-REN Alfréd Rényi Institute of Mathematics

George Giapitzakis, University of Waterloo

Alessandro Luongo, National University of Singapore

Aditya Morolia, National University of Singapore

Abstract

One of the main candidates of post-quantum cryptography is lattice-based cryptography. Its cryptographic security against quantum attackers is based on the worst-case hardness of lattice problems like the shortest vector problem (SVP), which asks to find the shortest non-zero vector in an integer lattice. Asymptotic quantum speedups for solving SVP are known and rely on Grover's search. However, to assess the security of lattice-based cryptography against these Grover-like quantum speedups, it is necessary to carry out a precise resource estimation beyond asymptotic scalings. In this work, we perform a careful analysis on the resources required to implement several sieving algorithms aided by Grover's search for dimensions of cryptographic interests. For such, we take into account fixed-point quantum arithmetic operations, non-asymptotic Grover's search, the cost of using quantum random access memory (QRAM), different physical architectures, and quantum error correction. We find that even under very optimistic assumptions like circuit-level noise of , code cycles of 100 ns, reaction time of 1 s, and using state-of-the-art arithmetic circuits and quantum error-correction protocols, the best sieving algorithms require physical qubits and years to solve SVP on a lattice of dimension 400, which is roughly the dimension for minimally secure post-quantum cryptographic standards currently being proposed by NIST. We estimate that a 6-GHz-clock-rate single-core classical computer would take roughly the same amount of time to solve the same problem. We conclude that there is currently little to no quantum speedup in the dimensions of cryptographic interest and the possibility of realising a considerable quantum speedup using quantum sieving algorithms would require significant breakthroughs in theoretical protocols and hardware development.

Note: 60+4 pages, 7+4 figures. v2: references added, results extended up to lattice dimension 1000

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: lattice sieves quantum computing cryptanalysis post-quantum public-key cryptography
Contact author(s): doriguello @ renyi hu
ggiapitz @ uwaterloo ca
ale @ nus edu sg
morolia @ u nus edu sg
History: 2025-02-17: revised; 2024-10-17: received; See all versions
Short URL: https://ia.cr/2024/1692
License: CC BY

BibTeX

@misc{cryptoeprint:2024/1692,
      author = {Joao F. Doriguello and George Giapitzakis and Alessandro Luongo and Aditya Morolia},
      title = {On the practicality of quantum sieving algorithms for the shortest vector problem},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1692},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1692}
}