Several Improvements on BKZ Algorithm

Ziyu Zhao Tsinghua University, Beijing Jintai Ding Tsinghua University, Beijing

TBD mathscidoc:2207.43133

IACR Cryptol. ePrint Arch., 2022.2
Lattice problem such as NTRU problem and LWE problem is 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 it. In this paper, we give several further improvements on BKZ algorithm, which can be used for different SVP subroutines base on both enumeration and sieving. These improvements in combination provide a speed up of 2^{3~4} in total. It is significant in concrete attacks. Using these new techniques, we solved the 656 dimensional ideal lattice challenge in only 380 thread hours (also with a enumeration based SVP subroutine), much less than the previous records (which costs 4600 thread hours in total). With these improvements enabled, we can still simulate the new BKZ algorithm easily. One can also use this simulator to find the blocksize strategy (and the corresponding cost) to make Pot of the basis (defined in section 5.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.
No keywords uploaded!
[ Download ] [ 2022-07-23 10:56:26 uploaded by dingjt ] [ 36 downloads ] [ 0 comments ]
  title={Several Improvements on BKZ Algorithm},
  author={Ziyu Zhao, and Jintai Ding},
  booktitle={IACR Cryptol. ePrint Arch.},
Ziyu Zhao, and Jintai Ding. Several Improvements on BKZ Algorithm. 2022. In IACR Cryptol. ePrint Arch..
Please log in for comment!
Contact us: | Copyright Reserved