%0 Journal Article
%T Rejecting Claimed Speedup of 2^𝛽/2 in Extreme Pruning and Revising BKZ 2.0 for Better Speedup
%J Journal of Computing and Security
%I University of Isfahan & Iranian Society of Cryptology
%Z 2322-4460
%A Moghissi, Gholam Reza
%A Payandeh, Ali
%D 2021
%\ 01/01/2021
%V 8
%N 1
%P 65-91
%! Rejecting Claimed Speedup of 2^𝛽/2 in Extreme Pruning and Revising BKZ 2.0 for Better Speedup
%K Extreme Pruning
%K GNR Enumeration
%K Cost Speedup
%K BKZ 2.0
%K BKZ Revised
%R 10.22108/jcs.2021.121191.1044
%X 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 ) ).
%U https://jcomsec.ui.ac.ir/article_25930_f75af66573cefafc2dfc988055b52003.pdf