Paper 2018/546

Quantum Lattice Enumeration and Tweaking Discrete Pruning

Yoshinori Aono, Phong Q. Nguyen, and 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2018
Keywords
LatticesQuantum algorithmsEnumeration
Contact author(s)
Phong Nguyen @ inria fr
History
2018-09-07: revised
2018-06-04: received
See all versions
Short URL
https://ia.cr/2018/546
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/546,
      author = {Yoshinori Aono and Phong Q.  Nguyen and Yixin Shen},
      title = {Quantum Lattice Enumeration and Tweaking Discrete Pruning},
      howpublished = {Cryptology ePrint Archive, Paper 2018/546},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/546}},
      url = {https://eprint.iacr.org/2018/546}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.