Paper 2018/586

Lower Bounds on Lattice Enumeration with Extreme Pruning

Yoshinori Aono, Phong Q. Nguyen, Takenobu Seito, and Junji Shikata

Abstract

At Eurocrypt '10, Gama, Nguyen and Regev introduced lattice enumeration with extreme pruning: this algorithm is implemented in state-of-the-art lattice reduction software and used in challenge records. They showed that extreme pruning provided an exponential speed-up over full enumeration. However, no limit on its efficiency was known, which was problematic for long-term security estimates of lattice-based cryptosystems. We prove the first lower bounds on lattice enumeration with extreme pruning: if the success probability is lower bounded, we can lower bound the global running time taken by extreme pruning. Our results are based on geometric properties of cylinder intersections and some form of isoperimetry. We discuss their impact on lattice security estimates.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in CRYPTO 2018
Keywords
LatticesEnumerationPruningSecurity Estimates
Contact author(s)
Phong Nguyen @ inria fr
History
2018-06-28: revised
2018-06-12: received
See all versions
Short URL
https://ia.cr/2018/586
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/586,
      author = {Yoshinori Aono and Phong Q.  Nguyen and Takenobu Seito and Junji Shikata},
      title = {Lower Bounds on Lattice Enumeration with Extreme Pruning},
      howpublished = {Cryptology ePrint Archive, Paper 2018/586},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/586}},
      url = {https://eprint.iacr.org/2018/586}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.