Preprocessing optimisation: revisiting recursive‐BKZ lattice reduction algorithm. (1st November 2018)

• Record Type: Journal Article
• Authors: Haque, Md. Mokammel; Pieprzyk, Josef
• Is Part Of: IET information security. Volume 12:Number 6(2018)
• Page Start: 551
• Page End: 557
• Publication Date: 2018-11-01
• Subjects: polynomials -- cryptography -- vectors -- MIMO communication -- computational complexity -- lattice theory -- matrix algebra; lattice reduction algorithms -- block Korkine–Zolotarev -- search time -- enumeration tree -- shortest vector -- classical form -- authors observe -- polynomial time Lenstra–Lenstra–Lovász algorithm -- slow enumeration -- enumeration stages -- time complexity -- preprocessing approach -- preprocessing optimisation -- recursive‐BKZ lattice reduction algorithm; Computer security -- Periodicals; Cryptography -- Periodicals; Computer networks -- Security measures -- Periodicals; Database security -- Periodicals; 005.8
• DOI: 10.1049/iet-ifs.2017.0400
• Languages: English
• ISSNs: 1751-8709

Abstract

Abstract : Preprocessing is applied to certain lattice reduction algorithms such as block Korkine–Zolotarev (BKZ) variants to reduce the search time in the enumeration tree for a shortest vector. The most classical form of preprocessing the authors observe is with polynomial time Lenstra–Lenstra–Lovász algorithm to work with a slow enumeration‐based algorithm like BKZ. The trade‐off between the preprocessing and the enumeration stages in the context of time complexity of the whole algorithm is not well studied and explored. The main goal of this study is to re‐investigate the preprocessing approach presented by Chen and Nguyen and improve its performance through optimisation. They extend the numeral results published by Haque et al . in IET Inf. Secur . for larger block sizes and report a comparison.