A New Self-dual BKZ Algorithm Based on Lattice Sieving

Lattice reduction algorithm is an important algorithm for solving lattice Shortest Vector Problem (SVP), which makes it the primary tool for evaluating the security of lattice-based cryptographic schemes. Lattice reduction algorithm’s running time and memory depend on the SVP-Oracle used as a subroutine. In this work, we use lattice sieving algorithm as the SVP-Oracle, combined with the Self-Dual BKZ algorithm, to design a new lattice reduction algorithm. Compared to the previous implementations based on enumeration algorithm, our new algorithm can produce more accurate results in less time. In addition, our new algorithm maintains the same computational performance as the state-of-the-art, i.e. the pump and jump BKZ.