Optimizing preprocessing method of recursive-BKZ lattice reduction algorithm

Md. Mokammel Haque; Josef Pieprzyk

doi:10.1109/EICT.2015.7391915

Optimizing preprocessing method of recursive-BKZ lattice reduction algorithm

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-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 language	English
Title of host publication	EICT 2015
Subtitle of host publication	proceedings of the 2nd International Conference on Electrical Information and Communication Technologies
Place of Publication	Piscataway, NJ
Publisher	Institute of Electrical and Electronics Engineers (IEEE)
Pages	19-23
Number of pages	5
ISBN (Electronic)	9781467392570, 9781467392556
ISBN (Print)	9781467392563
DOIs	https://doi.org/10.1109/EICT.2015.7391915
Publication status	Published - 2015
Externally published	Yes
Event	2nd International Conference on Electrical Information and Communication Technologies, EICT 2015 - Khulna, Bangladesh Duration: 10 Dec 2015 → 12 Dec 2015

Other

Other	2nd International Conference on Electrical Information and Communication Technologies, EICT 2015
Country/Territory	Bangladesh
City	Khulna
Period	10/12/15 → 12/12/15

Access to Document

10.1109/EICT.2015.7391915

Cite this

@inproceedings{9e630f93c8e445dda056165c26844e9e,

title = "Optimizing preprocessing method of recursive-BKZ lattice reduction algorithm",

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.",

author = "{Mokammel Haque}, Md. and Josef Pieprzyk",

year = "2015",

doi = "10.1109/EICT.2015.7391915",

language = "English",

isbn = "9781467392563",

pages = "19--23",

booktitle = "EICT 2015",

publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

address = "United States",

note = "2nd International Conference on Electrical Information and Communication Technologies, EICT 2015 ; Conference date: 10-12-2015 Through 12-12-2015",

}

Mokammel Haque, M & Pieprzyk, J 2015, Optimizing preprocessing method of recursive-BKZ lattice reduction algorithm. in EICT 2015: proceedings of the 2nd International Conference on Electrical Information and Communication Technologies. Institute of Electrical and Electronics Engineers (IEEE), Piscataway, NJ, pp. 19-23, 2nd International Conference on Electrical Information and Communication Technologies, EICT 2015, Khulna, Bangladesh, 10/12/15. https://doi.org/10.1109/EICT.2015.7391915

Optimizing preprocessing method of recursive-BKZ lattice reduction algorithm. / Mokammel Haque, Md.; Pieprzyk, Josef.

EICT 2015: proceedings of the 2nd International Conference on Electrical Information and Communication Technologies. Piscataway, NJ : Institute of Electrical and Electronics Engineers (IEEE), 2015. p. 19-23.

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - Optimizing preprocessing method of recursive-BKZ lattice reduction algorithm

AU - Mokammel Haque, Md.

AU - Pieprzyk, Josef

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84962791717&partnerID=8YFLogxK

U2 - 10.1109/EICT.2015.7391915

DO - 10.1109/EICT.2015.7391915

M3 - Conference proceeding contribution

AN - SCOPUS:84962791717

SN - 9781467392563

SP - 19

EP - 23

BT - EICT 2015

PB - Institute of Electrical and Electronics Engineers (IEEE)

CY - Piscataway, NJ

T2 - 2nd International Conference on Electrical Information and Communication Technologies, EICT 2015

Y2 - 10 December 2015 through 12 December 2015

ER -

Optimizing preprocessing method of recursive-BKZ lattice reduction algorithm

Abstract

Other

Access to Document

Other files and links

Fingerprint

Cite this