University of Isfahan & Iranian Society of CryptologyJournal of Computing and Security2322-44608120210101Rejecting Claimed Speedup of 2^𝛽/2 in Extreme Pruning and Revising BKZ 2.0 for Better Speedup65912593010.22108/jcs.2021.121191.1044ENGholam RezaMoghissiICT Department, Malek-Ashtar University of Technology, Tehran, Iran.0000-0001-9189-6786AliPayandehICT Department, Malek-Ashtar University of Technology, Tehran, Iran.Journal Article20200120 <br />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 ) ). https://jcomsec.ui.ac.ir/article_25930_f75af66573cefafc2dfc988055b52003.pdf