Paper 2022/468

Improved Pump and Jump BKZ by Sharp Simulator

Leizhang Wang, Wenwen Xia, Geng Wang, Baocang Wang, and Dawu Gu

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.

Note: There are many simulators of lattice reduction algorithms like BKZ, BKZ2.0, Progressive-BKZ which can accurately predict how the quality of output basis change during reducing. pnj-BKZ as currently the fastest lattice reduction algorithm, however there is no accurate simulator for pnj-BKZ when jump>1. Since these simulators of classical lattice reduction algorithms can only predict the value of jump equal to 1. By constructing simulator for pnj-BKZ when jump>1, we can find more efficient lattice reducation strategy to solve these approximate-SVP on lattice like (M)LWE and (M)SIS which are the hard problems that almost all lattice based cryptographic schemes' security based on. Therefore, it is of great significance to study how much improvement the jump technology can bring to the lattice reduction algorithm in order to accurately evaluate the concrete security strength of lattice based cryptographic schemes.In this paper, we proposed pnj-BKZ simulator by using the information of HKZ basis when jump>1. The results of experiments show that we can simulate well that how lattice basis changed in each tour of pnj-BKZ when jump>1. In addition, we use this pnj-BKZ simulator to give a optimized jump choosing strategy. In the end, using optimized jump choosing strategy, we can solve TU LWE challenge \footnote{TU LWE Challenge presents sample instances for testing algorithms that solve the LWE problem. The main goal of this challenge is to help assessing the hardness of the LWE problem in practice. Here is the link to this challenge: https://www.latticechallenge.org/lwe_challenge/challenge.php} ( n=75,\alpha=0.005 ) 2.9 times faster than that of G6K's default LWE sloving strategy.