Paper 2020/1237

A Complete Analysis of the BKZ Lattice Reduction Algorithm

Jianwei Li and Phong Q. Nguyen

Abstract

We present the first rigorous dynamic analysis of BKZ, the most widely used lattice reduction algorithm besides LLL. Previous analyses were either heuristic or only applied to variants of BKZ. Namely, we provide guarantees on the quality of the current lattice basis during execution. 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. Interestingly, it also provides currently the best and simplest bounds for both the output quality and the running time. 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
Preprint. MINOR revision.
Keywords
Lattice ReductionBKZDynamical Systemsand Enumeration
Contact author(s)
lijianweisk @ sina com
History
2022-03-05: last of 3 revisions
2020-10-09: received
See all versions
Short URL
https://ia.cr/2020/1237
License
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2020/1237}},
      url = {https://eprint.iacr.org/2020/1237}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.