Cryptology ePrint Archive: Report 2016/146
Improved Progressive BKZ Algorithms and their Precise Cost Estimation by Sharp Simulator
Yoshinori Aono and Yuntao Wang and Takuya Hayashi and Tsuyoshi Takagi
Abstract: In this paper, we investigate a variant of the BKZ algorithm,
called progressive BKZ, which performs BKZ reductions
by starting with a small blocksize and gradually switching to larger
blocks as the process continues. We discuss techniques to accelerate the speed of the
progressive BKZ algorithm by optimizing the following parameters:
blocksize, searching radius and probability for pruning of the local enumeration algorithm,
and the constant in the geometric series assumption (GSA).
We then propose a simulator for predicting the length
of the Gram-Schmidt basis obtained from the BKZ reduction.
We also present a model for estimating the
computational cost of the proposed progressive BKZ by
considering the efficient implementation of the local
enumeration algorithm and the LLL algorithm.
Finally, we compare the cost of the proposed progressive
BKZ with that of other algorithms using instances from the Darmstadt SVP Challenge.
The proposed algorithm is approximately 50 times faster than BKZ 2.0 (proposed by Chen-Nguyen) for
solving the SVP Challenge up to 160 dimensions.
Category / Keywords: foundations / Lattice basis reduction, progressive BKZ, Gram-Schmidt orthogonal basis, geometric series assumption
Original Publication (with minor differences): IACR-EUROCRYPT-2016
Date: received 16 Feb 2016, last revised 6 May 2016
Contact author: aono at nict go jp
Available format(s): PDF | BibTeX Citation
Version: 20160507:021544 (All versions of this report)
Short URL: ia.cr/2016/146
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]