TY - GEN
T1 - Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator
AU - Aono, Yoshinori
AU - Wang, Yuntao
AU - Hayashi, Takuya
AU - Takagi, Tsuyoshi
N1 - Funding Information:
Y. Aono—This work was supported by JSPS KAKENHI Grant Number 26730069.
Publisher Copyright:
© International Association for Cryptologic Research 2016.
PY - 2016
Y1 - 2016
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84979052734&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84979052734&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-49890-3_30
DO - 10.1007/978-3-662-49890-3_30
M3 - Conference contribution
AN - SCOPUS:84979052734
SN - 9783662498897
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 789
EP - 819
BT - Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
A2 - Fischlin, Marc
A2 - Coron, Jean-Sebastien
PB - Springer Verlag
T2 - 35th Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT 2016
Y2 - 8 May 2016 through 12 May 2016
ER -