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

Martin R.  Albrecht; Shi Bai; Pierre-Alain Fouque; Paul Kirchner; Damien Stehlé; Weiqiang Wen

Paper 2020/707

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

Martin R. Albrecht, Shi Bai, Pierre-Alain Fouque, Paul Kirchner, Damien Stehlé, and Weiqiang Wen

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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A minor revision of an IACR publication in CRYPTO 2020
Keywords: lattice techniques
Contact author(s): martin albrecht @ royalholloway ac uk
sbai @ fau edu
pierre-alain fouque @ univ-rennes1 fr
paul kirchner @ irisa fr
damien stehle @ ens-lyon fr
weiqiang a wen @ inria fr
History: 2020-06-14: received
Short URL: https://ia.cr/2020/707
License: CC BY

BibTeX

@misc{cryptoeprint:2020/707,
      author = {Martin R.  Albrecht and Shi Bai and Pierre-Alain Fouque and Paul Kirchner and Damien Stehlé and Weiqiang Wen},
      title = {Faster Enumeration-based Lattice Reduction: Root Hermite Factor k^(1/(2k)) in Time k^(k/8 + o(k))},
      howpublished = {Cryptology ePrint Archive, Paper 2020/707},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/707}},
      url = {https://eprint.iacr.org/2020/707}
}