Analysing recursive preprocessing of BKZ lattice reduction algorithm

作者：Haque Md Mokammel^*; Pieprzyk Josef

来源：IET Information Security, 2017, 11(2): 114-120.

DOI：10.1049/iet-ifs.2016.0049

• sandpile models
• cryptography
• approximation theory
• computational complexity
• vectors
• recursive-BKZ preprocessing model
• BKZ lattice reduction algorithm
• lattice problems
• cryptography
• shortest vector problem
• approximate variants
• block Korkine-Zolotarev algorithm
• pruning parameter optimisation
• preprocessing parameter optimisation
• approximate closed-form complexity formulas
• sandpile model
• enumeration time
• extreme pruning bounding profiles
• complexity upper bound estimate analysis

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 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. The authors optimise 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. The authors derive approximate closed-form complexity formulas (based on the sandpile model assumption model by Hanrot et al.) for the enumeration time which allow a simple estimation of complexity without running the simulation algorithm (by Chen and Nguyen) and asymptotically suggests a modified extreme pruning bounding profiles with different parameters. Hence, the authors' contributions are in optimising and improving the analysis of the complexity upper bound estimates presented by Chen and Nguyen, based on the same recursive-BKZ preprocessing model.

• 出版日期2017-3