Cryptology ePrint Archive: Report 2020/707

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

Martin R. Albrecht and Shi Bai and Pierre-Alain Fouque and Paul Kirchner and 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.

Category / Keywords: public-key cryptography / lattice techniques

Original Publication (with minor differences): IACR-CRYPTO-2020

Date: received 12 Jun 2020

Contact author: martin albrecht at 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

Available format(s): PDF | BibTeX Citation

Version: 20200614:201811 (All versions of this report)

Short URL: ia.cr/2020/707


[ Cryptology ePrint archive ]