Cryptology ePrint Archive: Report 2017/730

Second Order Statistical Behavior of LLL and BKZ

Yang Yu and Léo Ducas

Abstract: The LLL algorithm (from Lenstra, Lenstra and Lovász) and its generalization BKZ (from Schnorr and Euchner) are widely used in cryptanalysis, especially for lattice-based cryptography. Precisely understanding their behavior is crucial for deriving appropriate key-size for cryptographic schemes subject to lattice-reduction attacks. Current models, e.g. the Geometric Series Assumption and Chen-Nguyen's BKZ-simulator, have provided a decent first-order analysis of the behavior of LLL and BKZ. However, they only focused on the average behavior and were not perfectly accurate. In this work, we initiate a second order analysis of this behavior. We confirm and quantify discrepancies between models and experiments ---in particular in the head and tail regions--- and study their consequences. We also provide variations around the mean and correlations statistics, and study their impact. While mostly based on experiments, by pointing at and quantifying unaccounted phenomena, our study sets the ground for a theoretical and predictive understanding of LLL and BKZ performances at the second order.

Category / Keywords: public-key cryptography / Lattice reduction, LLL, BKZ, Cryptanalysis, Statistics

Original Publication (with minor differences): Accepted to SAC 2017

Date: received 27 Jul 2017

Contact author: y-y13 at mails tsinghua edu cn

Available format(s): PDF | BibTeX Citation

Version: 20170731:155028 (All versions of this report)

Short URL: ia.cr/2017/730

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]