Paper 2016/146

Improved Progressive BKZ Algorithms and their Precise Cost Estimation by Sharp Simulator

Yoshinori Aono, Yuntao Wang, 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in EUROCRYPT 2016
Keywords
Lattice basis reductionprogressive BKZGram-Schmidt orthogonal basisgeometric series assumption
Contact author(s)
aono @ nict go jp
History
2016-05-07: last of 2 revisions
2016-02-18: received
See all versions
Short URL
https://ia.cr/2016/146
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/146,
      author = {Yoshinori Aono and Yuntao Wang and Takuya Hayashi and Tsuyoshi Takagi},
      title = {Improved Progressive BKZ Algorithms and their Precise Cost Estimation by Sharp Simulator},
      howpublished = {Cryptology ePrint Archive, Paper 2016/146},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/146}},
      url = {https://eprint.iacr.org/2016/146}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.