International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Faster Enumeration-based Lattice Reduction: Root Hermite Factor k^(1/(2k)) in Time k^(k/8 + o(k))

Authors:
Martin Albrecht , Royal Holloway, University of London
Shi Bai , Department of Mathematical Sciences, Florida Atlantic University
Pierre-Alain Fouque , Univ. Rennes, CNRS, IRISA, Rennes, France
Paul Kirchner , Univ. Rennes, CNRS, IRISA, Rennes, France
Damien Stehlé , Univ. Lyon, EnsL, UCBL, CNRS, Inria, LIP, F-69342 Lyon Cedex 07, France
Weiqiang Wen , Univ. Rennes, CNRS, IRISA, Rennes, France
Download:
DOI: https://doi.org/10.1007/978-3-030-56880-1_7 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2020
Abstract: We give a lattice reduction algorithm that achieves root Hermite factor k^(1/(2k)) in time k^(k/8 + o(k)) and polynomial memory. This improves on the previously best known enumeration-based algorithms which achieve the same quality, but in time k^(k/(2e) + o(k)). A cost of k^(k/8 + o(k)) was previously mentioned as potentially achievable (Hanrot-Stehlé’10) or as a heuristic lower bound (Nguyen’10) for enumeration algorithms. We prove the complexity and quality of our algorithm under a heuristic assumption and provide empirical evidence from simulation and implementation experiments attesting to its performance for practical and cryptographic parameter sizes. Our work also suggests potential avenues for achieving costs below k^(k/8 + o(k)) for the same root Hermite factor, based on the geometry of SDBKZ-reduced bases.
Video from CRYPTO 2020
BibTeX
@inproceedings{crypto-2020-30367,
  title={Faster Enumeration-based Lattice Reduction: Root Hermite Factor k^(1/(2k)) in Time k^(k/8 + o(k))},
  publisher={Springer-Verlag},
  doi={https://doi.org/10.1007/978-3-030-56880-1_7},
  author={Martin Albrecht and Shi Bai and Pierre-Alain Fouque and Paul Kirchner and Damien Stehlé and Weiqiang Wen},
  year=2020
}