Paper 2021/570 Original: eprint.iacr.org/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
- Preprint.
- History
- 2023-02-22: last updated
- 2021-05-03: published
- Short URL
- https://ia.cr/2021/570
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2021/570}
}