Paper 2018/856

Measuring, simulating and exploiting the head concavity phenomenon in BKZ

Shi Bai, 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in ASIACRYPT 2018
Keywords
BKZ algorithmsimulator
Contact author(s)
weiqiang wen @ ens-lyon fr
History
2018-09-20: received
Short URL
https://ia.cr/2018/856
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/856,
      author = {Shi Bai and Damien Stehlé and Weiqiang Wen},
      title = {Measuring, simulating and exploiting the head concavity phenomenon in BKZ},
      howpublished = {Cryptology ePrint Archive, Paper 2018/856},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/856}},
      url = {https://eprint.iacr.org/2018/856}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.