@article {
author = {Moghissi, Gholam Reza and Payandeh, Ali},
title = {Rejecting Claimed Speedup of 2^𝛽/2 in Extreme Pruning and Revising BKZ 2.0 for Better Speedup},
journal = {Journal of Computing and Security},
volume = {8},
number = {1},
pages = {65-91},
year = {2021},
publisher = {University of Isfahan & Iranian Society of Cryptology},
issn = {2322-4460},
eissn = {2383-0417},
doi = {10.22108/jcs.2021.121191.1044},
abstract = { BKZ 2.0 algorithm is one of the claimant lattice reduction algorithms which incorporates extreme pruning as its main phase. The non-extreme pruning and extreme pruning in the original paper by Gamma-Nguyen-Regev (in 2010) respectively are claimed to reach the maximum speedup of 2^(β/4) and 2^(β/2) over full-enumeration. For 37≤β, this paper verifies the claimed speedup of 2^(β/4) by an optimal non-extreme pruned enumeration, while for a practical block size of 100≤β≤250, the upper-bound for speedup of extreme-pruned enumeration when blocks are preprocessed by BKZ with enumeration (as SVP-solver) is estimated from 2^(β/6.6) to 2^(β/4.4), and when blocks are preprocessed by BKZ with sieving is estimated from 2^(β/9.8) to 2^(β/3.4) ! By using these upper-bounds for speedup by extreme-pruning, all former security analyses which use the claimed speedup of 2^(β/2), should be revised (or rejected). Also, this paper proposes a revised version of BKZ 2.0, so that for a practical block size of 100≤β≤250 and an infinite number of rounds N≈∞, the lower-bound of its speedup over BKZ 2.0 is estimated by a factor of ρ_0 in range of 2^12≤ρ_0≤2^15.5 when blocks are preprocessed by BKZ with enumeration, and also lower-bound of its speedup is estimated in the range of 0≤ρ_0≤2^20.5 when blocks are preprocessed by BKZ with sieving. Moreover, for a finite number of rounds N, speedup of our revised BKZ 2.0 over original BKZ 2.0 can be estimated by O(min(N,ρ_0 ) ). },
keywords = {Extreme Pruning,GNR Enumeration,Cost Speedup,BKZ 2.0,BKZ Revised},
url = {https://jcomsec.ui.ac.ir/article_25930.html},
eprint = {https://jcomsec.ui.ac.ir/article_25930_f75af66573cefafc2dfc988055b52003.pdf}
}