Welcome to the resource topic for 2018/546
Title:
Quantum Lattice Enumeration and Tweaking Discrete Pruning
Authors: Yoshinori Aono, Phong Q. Nguyen, Yixin Shen
Abstract:Enumeration is a fundamental lattice algorithm used in challenge records. We show how to speed up enumeration on a quantum computer, which affects the security estimates of several lattice-based submissions to NIST: if T is the number of operations of enumeration, our quantum enumeration runs in roughly \sqrt{T} operations. This applies to the two most efficient forms of enumeration known in the extreme pruning setting: cylinder pruning but also discrete pruning introduced at Eurocrypt '17. Our results are based on recent quantum tree algorithms by Montanaro and Ambainis-Kokainis. The discrete pruning case requires a crucial tweak: we modify the preprocessing so that the running time can be rigorously proved to be essentially optimal, which was the main open problem in discrete pruning. We also introduce another tweak to solve the more general problem of finding close lattice vectors.
ePrint: https://eprint.iacr.org/2018/546
Slides: https://asiacrypt.iacr.org/2018/files/SLIDES/MONDAY/514/1330-1445/asiacrypt.pdf
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 .