Rejecting Claimed Speedup of ۲^𝛽/۲ in Extreme Pruning and Revising BKZ ۲.۰ for Better Speedup

 BKZ ۲.۰ 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 ۲۰۱۰) respectively are claimed to reach the maximum speedup of ۲^(β/۴) and ۲^(β/۲) over full-enumeration. For ۳۷≤β, this paper verifies the claimed speedup of ۲^(β/۴) by an optimal non-extreme pruned enumeration, while for a practical block size of ۱۰۰≤β≤۲۵۰, the upper-bound for speedup of extreme-pruned enumeration when blocks are preprocessed by BKZ with enumeration (as SVP-solver) is estimated from ۲^(β/۶.۶) to ۲^(β/۴.۴), and when blocks are preprocessed by BKZ with sieving is estimated from ۲^(β/۹.۸) to ۲^(β/۳.۴) ! By using these upper-bounds for speedup by extreme-pruning, all former security analyses which use the claimed speedup of ۲^(β/۲), should be revised  (or rejected). Also, this paper proposes a revised version of BKZ ۲.۰, so that for a practical block size of ۱۰۰≤β≤۲۵۰ and an infinite number of rounds N≈∞, the lower-bound of its speedup over BKZ ۲.۰ is estimated by a factor of ρ_۰ in range of ۲^۱۲≤ρ_۰≤۲^۱۵.۵ when blocks are preprocessed by BKZ with enumeration, and also lower-bound of its speedup is estimated in the range of ۰≤ρ_۰≤۲^۲۰.۵ when blocks are preprocessed by BKZ with sieving. Moreover, for a finite number of rounds N, speedup of our revised BKZ ۲.۰ over original BKZ ۲.۰ can be estimated by O(min⁡(N,ρ_۰ ) ). 

Keywords:

Extreme Pruning , GNR Enumeration , Cost Speedup , BKZ ۲.۰ , BKZ Revised