November 30, 2022
Ziyu Zhao - Tsinghua University
Lattice problems such as NTRU problem and LWE problem are widely used as the security base of post-quantum cryptosystems. And currently doing lattice reduction by BKZ algorithm is the most efficient way to solve them. In this paper, we give 4 further improvements on BKZ algorithm, which can be used for SVP subroutines base on enumeration and sieving. These improvements in combination provide a speed up of 23~4 in total. So all the lattice-based NIST PQC candidates lose 3 ∼ 4 bits of security in concrete attacks. Using these new techniques, we solved the 656 and 700 dimensional ideal lattice challenge in 380 and 1787 thread hours, respectively. The cost of the first one (also used an enumeration based SVP subroutine) is much less than the previous records (4600 thread hours). With these improvements enabled, we can still simulate the new BKZ algorithm easily. One can also use the simulator to find the blocksize strategy (and the corresponding cost) that makes Pot of the basis (defined in Section 4.2) decrease as fast as possible, which means the length of the first basis vector decrease the fastest if we accept the GSA assumption. It is useful for analyzing concrete attacks on lattice-based cryptography.
