A software technique to speed up BKZ implementations

The security of many lattice-based cryptographic primitives depend to last improvements in lattice basis reduction.The family of BKZ algorithms is one of the main practical lattice basis reduction approaches which so much studiesfocused on improving the cost of them. In this paper we present a technique for software implementation of BKZ whichintroducing some non-negligible speedup. This technique is based on determining the local blocks which don’t need tobe processed (enumeration and LLL reduction). In fact, deterministic operations in BKZ algorithm causes that some localblocks don’t need to be processed. This technique can be used for all deterministic version of BKZ family. We introducedso efficient implementations for this technique (in some pseudo codes), so that, no overhead nearly be expected overoriginal BKZ. Finally we use some experimental results for our proposed technique which showing that we can ignoreprocessing of up to 18.38% of local blocks in BKZ running.

Keywords:

lattice reduction , BKZ , enumeration , tracking engine , software implementation