Paper 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision.Accepted to SAC 2017
Keywords
Lattice reductionLLLBKZCryptanalysisStatistics
Contact author(s)
y-y13 @ mails tsinghua edu cn
History
2017-07-31: received
Short URL
https://ia.cr/2017/730
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/730,
      author = {Yang Yu and Léo Ducas},
      title = {Second Order Statistical Behavior of LLL and BKZ},
      howpublished = {Cryptology ePrint Archive, Paper 2017/730},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/730}},
      url = {https://eprint.iacr.org/2017/730}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.