Paper 2011/198
Terminating BKZ
Guillaume Hanrot, Xavier Pujol, and Damien Stehlé
Abstract
Strong lattice reduction is the key element for most attacks against latticebased cryptosystems. Between the strongest but impractical HKZ reduction and the weak but fast LLL reduction, there have been several attempts to find efficient tradeoffs. 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 $(b_i)_{i\leq n} \in Q^{n \times n}$ of a lattice L and a blocksize $\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 HKZreduction (or SVP) subroutine, then BKZ returns a basis whose first vector has norm $\leq 2 \gamma_{\beta}^{\frac{n1}{2(\beta1)}+\frac{3}{2}} \cdot (\det L)^{\frac{1}{n}}$, where~$\gamma_{\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 discretetime affine dynamical systems, which could lead to the design of improved lattice reduction algorithms.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 Euclidean latticesBKZlatticebased cryptanalysis
 Contact author(s)
 xavier pujol @ enslyon fr
 History
 20110425: received
 Short URL
 https://ia.cr/2011/198
 License

CC BY
BibTeX
@misc{cryptoeprint:2011/198, author = {Guillaume Hanrot and Xavier Pujol and Damien Stehlé}, title = {Terminating BKZ}, howpublished = {Cryptology ePrint Archive, Paper 2011/198}, year = {2011}, note = {\url{https://eprint.iacr.org/2011/198}}, url = {https://eprint.iacr.org/2011/198} }