Leizhang Wang
date:2022/5/24
title:Introduction to the simulator of Pump and Jump BKZ and a better reducing strategy
Abstract:
Hard problems on lattice: Learning with Errors problem (LWE) play central role in cryptography for constructing quantum-safe cryptographic constructions. In order to estimate the concrete security strength of these lattice-based cryptographic schemes, generally, the LWE problem is first reduced to u-SVP on an embedding lattice, and then calculating the computational cost of lattice reduction algorithm solving the u-SVP on the embedding lattice. Furthermore, the simulator of lattice reduction algorithm was constructed to more accurately predict the behavior of lattice reduction algorithm and to construct a more efficient lattice reduction algorithm. However unlike classical lattice reduction algorithm BKZ, there is no simulator for predicting the behavior of the Pump and jump-BKZ (pnj-BKZ) algorithm when jump greater than 1, which is currently considered as the fastest lattice reduction algorithm proposed in General Sieve Kernel (G6K).
In this talk, I will firstly introduce that 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, I will present that based on our pnj-BKZ simulator and time cost model of pnj-BKZ, how we construct a more efficient lattice reduction algorithm which help us to solve TU LWE challenge (n=80, alpha=0.005 and n=40, alpha=0.035). Here is the link to this challenge: https://www.latticechallenge.org/lwe_challenge/challenge.php.
