A new BKZ-type reduction with provable termination and development of its self-dual variant

The block Korkine–Zolotarev (BKZ) algorithm is a strong reduction algorithm for solving lattice problems such as the shortest vector problem (SVP) and the closest vector problem (CVP). For a large blocksize $$\beta $$ , the BKZ algorithm requires many calls to an exact-SVP algorithm over a local projected block lattice of rank $$\beta $$ , and thus in practice it is customary to terminate the reduction process prematurely. In this paper, we propose a new BKZ-type algorithm with provable termination. We name it “PotBKZ" since we use the potential of a lattice basis. Specifically, we develop “PotENUM", an enumeration algorithm to find lattice vectors whose insertion can reduce the potential. In PotBKZ, we call PotENUM instead of an exact-SVP algorithm to reduce the potential monotonically. We prove that PotBKZ terminates in a polynomial number of calls to PotENUM. Furthermore, we develop a self-dual variant of PotBKZ to reduce the potential more effectively with provable termination.