International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Lattice sieving via quantum random walks

Authors:
Johanna Loyer , Inria
André Chailloux , Inria
Download:
DOI: 10.1007/978-3-030-92068-5_3
Search ePrint
Search Google
Conference: ASIACRYPT 2021
Abstract: 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.
Video from ASIACRYPT 2021
BibTeX
@inproceedings{asiacrypt-2021-31458,
  title={Lattice sieving via quantum random walks},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-030-92068-5_3},
  author={Johanna Loyer and André Chailloux},
  year=2021
}