Predicting tours and probabilistic simulation for BKZ lattice reduction algorithm

Md Mokammel Haque; Josef Pieprzyk; Asaduzzaman

doi:10.1109/IFOST.2014.6991058

Predicting tours and probabilistic simulation for BKZ lattice reduction algorithm

Md Mokammel Haque, Josef Pieprzyk, Asaduzzaman

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

Abstract

We investigate the terminating concept of BKZ reduction first introduced by Hanrot et al. [Crypto'11] and make extensive experiments to predict the number of tours necessary to obtain the best possible trade off between reduction time and quality. Then, we improve Buchmann and Lindner's result [Indocrypt'09] to find sub-lattice collision in SWIFFT. We illustrate that further improvement in time is possible through special setting of SWIFFT parameters and also through the combination of different reduction parameters adaptively. Our contribution also include a probabilistic simulation approach top-up deterministic simulation described by Chen and Nguyen [Asiacrypt'11] that can able to predict the Gram-Schmidt norms more accurately for large block sizes.

Original language	English
Title of host publication	IFOST 2014
Subtitle of host publication	Proceedings of the 9th International Forum on Strategic Technology
Place of Publication	Piscataway, NJ
Publisher	Institute of Electrical and Electronics Engineers (IEEE)
Pages	1-4
Number of pages	4
ISBN (Electronic)	9781479960620, 9781479960606
DOIs	https://doi.org/10.1109/IFOST.2014.6991058
Publication status	Published - 17 Dec 2014
Externally published	Yes
Event	9th International Forum on Strategic Technology, IFOST 2014 - Cox's Bazar, Bangladesh Duration: 21 Oct 2014 → 23 Oct 2014

Other

Other	9th International Forum on Strategic Technology, IFOST 2014
Country/Territory	Bangladesh
City	Cox's Bazar
Period	21/10/14 → 23/10/14

Keywords

BKZ
Cryptosystem
Hermite factor
Lattice reduction
SWIFFT

Access to Document

10.1109/IFOST.2014.6991058

Cite this

@inproceedings{3b7466251a8047b0a757b5163a534a79,

title = "Predicting tours and probabilistic simulation for BKZ lattice reduction algorithm",

abstract = "We investigate the terminating concept of BKZ reduction first introduced by Hanrot et al. [Crypto'11] and make extensive experiments to predict the number of tours necessary to obtain the best possible trade off between reduction time and quality. Then, we improve Buchmann and Lindner's result [Indocrypt'09] to find sub-lattice collision in SWIFFT. We illustrate that further improvement in time is possible through special setting of SWIFFT parameters and also through the combination of different reduction parameters adaptively. Our contribution also include a probabilistic simulation approach top-up deterministic simulation described by Chen and Nguyen [Asiacrypt'11] that can able to predict the Gram-Schmidt norms more accurately for large block sizes.",

keywords = "BKZ, Cryptosystem, Hermite factor, Lattice reduction, SWIFFT",

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

year = "2014",

month = dec,

day = "17",

doi = "10.1109/IFOST.2014.6991058",

language = "English",

pages = "1--4",

booktitle = "IFOST 2014",

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

address = "United States",

note = "9th International Forum on Strategic Technology, IFOST 2014 ; Conference date: 21-10-2014 Through 23-10-2014",

}

Haque, MM, Pieprzyk, J & Asaduzzaman 2014, Predicting tours and probabilistic simulation for BKZ lattice reduction algorithm. in IFOST 2014: Proceedings of the 9th International Forum on Strategic Technology. Institute of Electrical and Electronics Engineers (IEEE), Piscataway, NJ, pp. 1-4, 9th International Forum on Strategic Technology, IFOST 2014, Cox's Bazar, Bangladesh, 21/10/14. https://doi.org/10.1109/IFOST.2014.6991058

Predicting tours and probabilistic simulation for BKZ lattice reduction algorithm. / Haque, Md Mokammel; Pieprzyk, Josef; Asaduzzaman.
IFOST 2014: Proceedings of the 9th International Forum on Strategic Technology. Piscataway, NJ: Institute of Electrical and Electronics Engineers (IEEE), 2014. p. 1-4.

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

TY - GEN

T1 - Predicting tours and probabilistic simulation for BKZ lattice reduction algorithm

AU - Haque, Md Mokammel

AU - Pieprzyk, Josef

AU - Asaduzzaman,

PY - 2014/12/17

Y1 - 2014/12/17

N2 - We investigate the terminating concept of BKZ reduction first introduced by Hanrot et al. [Crypto'11] and make extensive experiments to predict the number of tours necessary to obtain the best possible trade off between reduction time and quality. Then, we improve Buchmann and Lindner's result [Indocrypt'09] to find sub-lattice collision in SWIFFT. We illustrate that further improvement in time is possible through special setting of SWIFFT parameters and also through the combination of different reduction parameters adaptively. Our contribution also include a probabilistic simulation approach top-up deterministic simulation described by Chen and Nguyen [Asiacrypt'11] that can able to predict the Gram-Schmidt norms more accurately for large block sizes.

AB - We investigate the terminating concept of BKZ reduction first introduced by Hanrot et al. [Crypto'11] and make extensive experiments to predict the number of tours necessary to obtain the best possible trade off between reduction time and quality. Then, we improve Buchmann and Lindner's result [Indocrypt'09] to find sub-lattice collision in SWIFFT. We illustrate that further improvement in time is possible through special setting of SWIFFT parameters and also through the combination of different reduction parameters adaptively. Our contribution also include a probabilistic simulation approach top-up deterministic simulation described by Chen and Nguyen [Asiacrypt'11] that can able to predict the Gram-Schmidt norms more accurately for large block sizes.

KW - BKZ

KW - Cryptosystem

KW - Hermite factor

KW - Lattice reduction

KW - SWIFFT

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

U2 - 10.1109/IFOST.2014.6991058

DO - 10.1109/IFOST.2014.6991058

M3 - Conference proceeding contribution

AN - SCOPUS:84921279153

SP - 1

EP - 4

BT - IFOST 2014

PB - Institute of Electrical and Electronics Engineers (IEEE)

CY - Piscataway, NJ

T2 - 9th International Forum on Strategic Technology, IFOST 2014

Y2 - 21 October 2014 through 23 October 2014

ER -

Predicting tours and probabilistic simulation for BKZ lattice reduction algorithm

Abstract

Other

Keywords

Access to Document

Other files and links

Fingerprint

Cite this