Skip to Main content Skip to Navigation
Conference papers

Quantum Lattice Enumeration and Tweaking Discrete Pruning

Abstract : Enumeration is a fundamental lattice algorithm. 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 $√ 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [45 references]  Display  Hide  Download

https://hal.inria.fr/hal-01870620
Contributor : Phong Q. Nguyen <>
Submitted on : Saturday, September 8, 2018 - 1:18:54 AM
Last modification on : Monday, May 17, 2021 - 12:00:05 PM
Long-term archiving on: : Sunday, December 9, 2018 - 12:35:06 PM

File

QuantumEnum-Eprint18.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01870620, version 1

Citation

Yoshinori Aono, Phong Q. Nguyen, Yixin Shen. Quantum Lattice Enumeration and Tweaking Discrete Pruning. Asiacrypt 2018 - the 24th Annual International Conference on the Theory and Application of Cryptology and Information Security, Dec 2018, Brisbane, Australia. ⟨hal-01870620⟩

Share

Metrics

Record views

442

Files downloads

569