Optimizing preprocessing method of recursive-BKZ lattice reduction algorithm
Md. Mokammel Haque, Josef Pieprzyk · 2015
Lattice problems are considered as the key elements in many areas of computer science as well as in cryptography; the most important of which is the shortest vector problem (called SVP in short) and its approximate variants. Algorithms for this problem are known as lattice reduction algorithms. Currently, the most practical lattice reduction algorithm for such problems is the Block-Korkine-Zolotarev (BKZ) algorithm and its variants. Preprocessing is a technique that can be applied to certain lattice reduction algorithms (such as BKZ variants) to reduce the search time in the enumeration tree for a shortest vector. We optimize both the pruning and the preprocessing parameters of the recursive (aborted, extreme pruned) preprocessing of the BKZ lattice reduction algorithm and improve the results from Asiacrypt'11 by Chen and Nguyen.