Paper 2021/570
Lattice sieving via quantum random walks
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.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- A minor revision of an IACR publication in ASIACRYPT 2021
- Keywords
- lattice-based cryptographySVPquantum random walkssieving algorithms
- Contact author(s)
-
andre chailloux @ inria fr
johanna loyer @ gmail com - History
- 2023-02-22: revised
- 2021-05-03: received
- See all versions
- Short URL
- https://ia.cr/2021/570
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2021/570,
author = {André Chailloux and Johanna Loyer},
title = {Lattice sieving via quantum random walks},
howpublished = {Cryptology ePrint Archive, Paper 2021/570},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/570}},
url = {https://eprint.iacr.org/2021/570}
}
