Analysing Progressive-BKZ Lattice Reduction Algorithm

Abstract

BKZ and its variants are considered as the most efficient lattice reduction algorithms compensating both the quality and runtime. Progressive approach (gradually increasing block size) of this algorithm has been attempted in several works for better performance but actual analysis of this approach has never been reported. In this paper, we plot experimental evidence of its complexity over the direct approach. We see that a considerable time saving can be achieved if we use the output basis of the immediately reduced block as the input basis of the current block (with increased block size) successively. Then, we attempt to find pseudo collision in SWIFFT hash function and show that a different set of parameters produces a special shape of Gram-Schmidt norms other than the predicted Geometric Series Assumptions (GSA) which the experiment suggests being more efficient.