## Analyzing Blockwise Lattice Algorithms using
Dynamical Systems

**Guillaume Hanrot, Xavier Pujol, and Damien Stehlé**

*
ÉNS Lyon, Laboratoire LIP, France;
ÉNS Lyon, Laboratoire LIP, France; and
CNRS, Laboratoire LIP, France
*
**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 practical
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 show that if given as inputs a
basis~$(\vec{b}_i)_{i\leq n} \in \mQ^{n \times n}$ of a lattice~$L$
and a block-size~$\beta$, and if terminated after
$\Omega\left(\frac{n^3}{\beta^2}(\log n + \log \log \max_i
\|\vec{b}_i\|)\right)$ calls to a $\beta$-dimensional
HKZ-reduction (or SVP) subroutine, then BKZ returns a basis
whose first vector has norm $\leq 2
\maxgamma_{\beta}^{\frac{n-1}{2(\beta-1)}+\frac{3}{2}} \cdot (\det L
)^{\frac{1}{n}}$, where~$\maxgamma_{\beta} \leq \beta$ is the maximum
of Hermite's constants in dimensions~$\leq \beta$. 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.