Cryptology ePrint Archive: Report 2018/856

Measuring, simulating and exploiting the head concavity phenomenon in BKZ

Shi Bai and Damien Stehlé and Weiqiang Wen

Abstract: The Blockwise-Korkine-Zolotarev (BKZ) lattice reduction algorithm is central in cryptanalysis, in particular for lattice-based cryptography. A precise understanding of its practical behavior in terms of run-time and output quality is necessary for parameter selection in cryptographic design. As the provable worst-case bounds poorly reflect the practical behavior, cryptanalysts rely instead on the heuristic BKZ simulator of Chen and Nguyen (Asiacrypt'11). It fits better with practical experiments, but not entirely. In particular, it over-estimates the norm of the first few vectors in the output basis. Put differently, BKZ performs better than its Chen-Nguyen simulation.

In this work, we first report experiments providing more insight on this shorter-than-expected phenomenon. We then propose a refined BKZ simulator by taking the distribution of short vectors in random lattices into consideration. We report experiments suggesting that this refined simulator more accurately predicts the concrete behavior of BKZ. Furthermore, we design a new BKZ variant that exploits the shorter-than-expected phenomenon. For the same cost assigned to the underlying SVP-solver, the new BKZ variant produces bases of better quality. We further illustrate its potential impact by testing it on the SVP-120 instance of the Darmstadt lattice challenge.

Category / Keywords: foundations / BKZ algorithm, simulator

Original Publication (with minor differences): IACR-ASIACRYPT-2018

Date: received 11 Sep 2018

Contact author: weiqiang wen at ens-lyon fr

Available format(s): PDF | BibTeX Citation

Version: 20180920:190442 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]