Optimizing preprocessing method of recursive-BKZ lattice reduction algorithm

Md. Mokammel Haque, Josef Pieprzyk

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

Abstract

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.

Original languageEnglish
Title of host publicationEICT 2015
Subtitle of host publicationproceedings of the 2nd International Conference on Electrical Information and Communication Technologies
Place of PublicationPiscataway, NJ
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages19-23
Number of pages5
ISBN (Electronic)9781467392570, 9781467392556
ISBN (Print)9781467392563
DOIs
Publication statusPublished - 2015
Externally publishedYes
Event2nd International Conference on Electrical Information and Communication Technologies, EICT 2015 - Khulna, Bangladesh
Duration: 10 Dec 201512 Dec 2015

Other

Other2nd International Conference on Electrical Information and Communication Technologies, EICT 2015
Country/TerritoryBangladesh
CityKhulna
Period10/12/1512/12/15

Fingerprint

Dive into the research topics of 'Optimizing preprocessing method of recursive-BKZ lattice reduction algorithm'. Together they form a unique fingerprint.

Cite this