Dynamic self-dual DeepBKZ lattice reduction with free dimensions and its implementation

Abstract Lattice problems are algorithmic problems for lattices, whose hardness assures the security of lattice-based cryptography. Given a basis of a lattice, the goal of lattice basis reduction is to seek a new basis of the same lattice whose basis vectors are relatively short and nearly orthogonal to each other. Such reduction algorithms give a fundamental tool to solve lattice problems such as the shortest and the closest vector problems. In this paper, we provide a new self-dual variant of the DeepBKZ reduction algorithm. Our variant dynamically switches performing primal and dual reductions for local blocks of an input basis to effectively reduce the whole basis. In particular, we introduce a parameter of free dimensions to determine the sizes of local blocks to be reduced. We also implement our self-dual DeepBKZ to report its experimental results for random lattice bases.