Welcome to the resource topic for 2021/570
Title:
Lattice sieving via quantum random walks
Authors: André Chailloux, Johanna Loyer
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.
ePrint: https://eprint.iacr.org/2021/570
Talk: https://www.youtube.com/watch?v=QOXS1HXsWZw
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .