Paper 2021/570

Lattice sieving via quantum random walks

André Chailloux, French Institute for Research in Computer Science and Automation
Johanna Loyer, French Institute for Research in Computer Science and Automation

Lattice-based cryptography is one of the leading proposals for post-quantum cryptography. The Shortest Vector Problem (SVP) is arguably the most important problem for the cryptanalysis of lattice-based cryptography, and many lattice-based schemes have security claims based on its hardness. The best quantum algorithm for the SVP is due to Laarhoven [Laa16 PhD] and runs in (heuristic) time $2^{0.2653d + o(d)}$. In this article, we present an improvement over Laarhoven's result and present an algorithm that has a (heuristic) running time of $2^{0.2570 d + o(d)}$ where $d$ is the lattice dimension. We also present time-memory trade-offs where we quantify the amount of quantum memory and quantum random access memory of our algorithm. The core idea is to replace Grover's algorithm used in [Laa16 PhD] in a key part of the sieving algorithm by a quantum random walk in which we add a layer of local sensitive filtering.

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in ASIACRYPT 2021
lattice-based cryptographySVPquantum random walkssieving algorithms
Contact author(s)
andre chailloux @ inria fr
johanna loyer @ gmail com
2023-02-22: revised
2021-05-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {André Chailloux and Johanna Loyer},
      title = {Lattice sieving via quantum random walks},
      howpublished = {Cryptology ePrint Archive, Paper 2021/570},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.