TY - JOUR
ID - 25930
TI - Rejecting Claimed Speedup of 2^𝛽/2 in Extreme Pruning and Revising BKZ 2.0 for Better Speedup
JO - Journal of Computing and Security
JA - JCS
LA - en
SN - 2322-4460
AU - Moghissi, Gholam Reza
AU - Payandeh, Ali
AD - ICT Department, Malek-Ashtar University of Technology, Tehran, Iran.
Y1 - 2021
PY - 2021
VL - 8
IS - 1
SP - 65
EP - 91
KW - Extreme Pruning
KW - GNR Enumeration
KW - Cost Speedup
KW - BKZ 2.0
KW - BKZ Revised
DO - 10.22108/jcs.2021.121191.1044
N2 - 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 ) ).
UR - https://jcomsec.ui.ac.ir/article_25930.html
L1 - https://jcomsec.ui.ac.ir/article_25930_f75af66573cefafc2dfc988055b52003.pdf
ER -