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 jumpBKZ (pnjBKZ) algorithm which is currently considered as the fastest lattice reduction algorithm. The pnjBKZ is a BKZtype 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 pnjBKZ algorithm when jump greater than 1, which is helpful to find a better lattice reduction strategy. There are two main differences between pnjBKZ and the classical BKZ algorithm: one is that after pnjBKZ performs the SVP Oracle on a certain projected sublattice, it won't calling SVP Oracle for the next nearest projected sublattice. Instead, pnjBKZ 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 pnjBKZ will be reduced to about 1/J times of original. The second is that pnjBKZ uses Pump as the SVP Oracle on the projected sublattice. Based on the BKZ2.0 simulator, we proposes a pnjBKZ simulator by using the properties of HKZ reduction basis. Experiments show that our proposed pnjBKZ simulator can well predicate the behavior of pnjBKZ with jump greater than 1. Besides, we use this pnjBKZ simulator to give the optimization strategy for choosing jump which can improve the reducing efficiency of pnjBKZ. Our optimized pnjBKZ 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, ProgressiveBKZ which can accurately predict how the quality of output basis change during reducing. pnjBKZ as currently the fastest lattice reduction algorithm, however there is no accurate simulator for pnjBKZ 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 pnjBKZ when jump>1, we can find more efficient lattice reducation strategy to solve these approximateSVP 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 pnjBKZ 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 pnjBKZ when jump>1. In addition, we use this pnjBKZ 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.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Preprint. Minor revision.
 Keywords
 pnjBKZ SimulatorOptimal Jump StrategyTU LWE ChallengeG6K
 Contact author(s)
 leizhangalpha @ 163 com
 History
 20220501: last of 3 revisions
 20220422: received
 See all versions
 Short URL
 https://ia.cr/2022/468
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/468, author = {Leizhang Wang and Wenwen Xia and Geng Wang and Baocang Wang and Dawu Gu}, title = {Improved Pump and Jump BKZ by Sharp Simulator}, howpublished = {Cryptology ePrint Archive, Paper 2022/468}, year = {2022}, note = {\url{https://eprint.iacr.org/2022/468}}, url = {https://eprint.iacr.org/2022/468} }