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
-
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},
url = {https://eprint.iacr.org/2017/730}
}
