文档介绍：Terminating BKZ
Guillaume Hanrot, Xavier Pujol, and Damien Stehlé
Laboratoire LIP (U. Lyon, CNRS, ENS Lyon, INRIA, UCBL),
46 Allée d’Italie, 69364 Lyon Cedex 07, France.
,,damien.******@ens-
Abstract. Strong lattice reduction is the key element for most attacks against lattice-based cryptosystems.
Between the strongest but impractical HKZ reduction and the weak but fast LLL reduction, there have been
several attempts to find efficient trade-offs. Among them, the BKZ algorithm introduced by Schnorr and Euchner
[FCT’91] seems to achieve the best time/quality compromise in practice. However, no reasonable complexity
upper bound is known for BKZ, and Gama and Nguyen [Eurocrypt’08] observed experimentally that its prac-
tical runtime seems to grow exponentially with the lattice dimension. In this work, we show that BKZ can
be terminated long before its completion, while still providing bases of excellent quality. More precisely, we
n×n
show that if given as inputs a basis (bi)i≤n ∈ Q of a lattice L and a block-size β, and if terminated after
“ n3 ”
Ω β2 (log n + log log maxi kbik) calls to a β-dimensional HKZ-reduction (or SVP) subroutine, then BKZ re-
n−1 3
2(β−1) + 2 1
n
turns a basis whose first vector has norm ≤ 2γβ · (det L) , where γβ ≤ β is the maximum of Hermite’s
constants in dimensions ≤ β. To obtain this result, we develop a completely new elementary technique based on
discrete-time affine dynamical systems, which could lead to the design of improved lattice reduction algorithms.
Keywords. Euclidean lattices, BKZ, lattice-based cryptanalysis.