Cryptology ePrint Archive: Report 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 quantitative improvements, such as better and simpler 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.

Category / Keywords: foundations / Lattice Reduction, BKZ , Dynamical Systems, and Enumeration

Date: received 7 Oct 2020, last revised 10 Oct 2020

Contact author: lijianweisk at sina com

Available format(s): PDF | BibTeX Citation

Version: 20201010:102815 (All versions of this report)

Short URL: ia.cr/2020/1237


[ Cryptology ePrint archive ]