Paper 2022/468 Original: eprint.iacr.org/2022/468 ↗

Improved Pump and Jump BKZ by Sharp Simulator

Abstract

The General Sieve Kernel (G6K) implemented a variety of lattice reduction algorithms based on sieving algorithms. One of the representative of these lattice reduction algorithms is Pump and jump-BKZ (pnj-BKZ) algorithm which is currently considered as the fastest lattice reduction algorithm. The pnj-BKZ is a BKZ-type lattice reduction algorithm which includes the jump strategy, and uses Pump as the SVP Oracle. Here, Pump which was also proposed in G6K, is an SVP sloving algorithm that combines progressive sieve technology and dimforfree technology. However unlike classical BKZ, there is no simulator for predicting the behavior of the pnj-BKZ algorithm when jump greater than 1, which is helpful to find a better lattice reduction strategy. There are two main differences between pnj-BKZ and the classical BKZ algorithm: one is that after pnj-BKZ performs the SVP Oracle on a certain projected sublattice, it won't calling SVP Oracle for the next nearest projected sublattice. Instead, pnj-BKZ jumps to the corresponding projected sublattice after J indexs to run the algorithm for solving the SVP. By using this jump technique, the number of times that the SVP algorithm needs to be called for each round of pnj-BKZ will be reduced to about 1/J times of original. The second is that pnj-BKZ uses Pump as the SVP Oracle on the projected sublattice. Based on the BKZ2.0 simulator, we proposes a pnj-BKZ simulator by using the properties of HKZ reduction basis. Experiments show that our proposed pnj-BKZ simulator can well predicate the behavior of pnj-BKZ with jump greater than 1. Besides, we use this pnj-BKZ simulator to give the optimization strategy for choosing jump which can improve the reducing efficiency of pnj-BKZ. Our optimized pnj-BKZ is 2.9 and 2.6 times faster in solving TU LWE challenge ( n=75,alpha=0.005 ) and TU LWE challenge ( n=60,alpha=0.010 ) than G6K's default LWE sloving strategy.