A Complete Analysis of the BKZ Lattice Reduction Algorithm

Jianwei Li; Phong Q.  Nguyen

Paper 2020/1237

A Complete Analysis of the BKZ Lattice Reduction Algorithm

Jianwei Li

, Inria and DIENS, PSL

Phong Q. Nguyen, Inria and DIENS, PSL

Abstract

We present the first rigorous dynamic analysis of BKZ, the most widely used lattice reduction algorithm besides LLL: we provide guarantees on the quality of the current lattice basis during execution. Previous analyses were either heuristic or only applied to theoretical variants of BKZ, not the real BKZ implemented in software libraries. Our analysis extends to a generic BKZ algorithm where the SVP-oracle is replaced by an approximate oracle and/or the basis update is not necessarily performed by LLL. As an application, we observe that in certain approximation regimes, it is more efficient to use BKZ with an approximate rather than exact SVP-oracle.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published by the IACR in JOC 2024
Keywords: Lattice Reduction BKZ Dynamical Systems and Enumeration
Contact author(s): lijianweisk @ sina com
Phong Nguyen @ inria fr
History: 2024-10-04: last of 5 revisions; 2020-10-09: received; See all versions
Short URL: https://ia.cr/2020/1237
License: CC BY

BibTeX

@misc{cryptoeprint:2020/1237,
      author = {Jianwei Li and Phong Q.  Nguyen},
      title = {A Complete Analysis of the {BKZ} Lattice Reduction Algorithm},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/1237},
      year = {2020},
      url = {https://eprint.iacr.org/2020/1237}
}