Preprocessing optimisation

revisiting recursive-BKZ lattice reduction algorithm

Md. Mokammel Haque, Josef Pieprzyk

Research output: Contribution to journalArticle

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.

Original languageEnglish
Pages (from-to)551-557
Number of pages7
JournalIET Information Security
Volume12
Issue number6
DOIs
Publication statusPublished - 1 Nov 2018
Externally publishedYes

Fingerprint Dive into the research topics of 'Preprocessing optimisation: revisiting recursive-BKZ lattice reduction algorithm'. Together they form a unique fingerprint.

  • Cite this