Presentation 2012-09-21
Heuristic improvements of BKZ 2.0
Yoshinori AONO, Ken NAGANUMA,
PDF Download Page PDF download Page Link
Abstract(in Japanese) (See Japanese page)
Abstract(in English) It has been considered an important problem to figure out practical intractability of the shortest (clos-est) vector problem of lattices because the security of several important cryptographic schemes can be reduced to the problem. In Asiacrypt 2011, Chen and Nguyen proposed the BKZ 2.0 algorithm, which has the best known performance for high dimensional lattices. They made new records of the challenge problems published in TU darmstadt lattice challenge at 525 to 800 dimensional lattices, and refined the security estimations of several cryptgraphic primitives. On the other hand, they left a few problems (i) appropriate parameter settings have never been known, and (ii) some heuristic improvements are possible. To investigate them, we implement their algorithm by using Shoup's NTL library and propose several heuristic improvements. Our algorithm has five times faster performance than the original BKZ 2.0 for 600 dimensional lattice of the challenge problem, and achieved new records at 500 to 675 dimensions. From the experiments, a vector that attains Hermite factor 1.01 can be found in one CPU week; this is about 42.25 bit security.
Keyword(in Japanese) (See Japanese page)
Keyword(in English) Lattice basis reduction / BKZ reduction algorithm / BKZ 2.0 / Lattice Challenge
Paper # ISEC2012-45
Date of Issue

Conference Information
Committee ISEC
Conference Date 2012/9/14(1days)
Place (in Japanese) (See Japanese page)
Place (in English)
Topics (in Japanese) (See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To Information Security (ISEC)
Language JPN
Title (in Japanese) (See Japanese page)
Sub Title (in Japanese) (See Japanese page)
Title (in English) Heuristic improvements of BKZ 2.0
Sub Title (in English)
Keyword(1) Lattice basis reduction
Keyword(2) BKZ reduction algorithm
Keyword(3) BKZ 2.0
Keyword(4) Lattice Challenge
1st Author's Name Yoshinori AONO
1st Author's Affiliation National Institute of Information and Communications Technology()
2nd Author's Name Ken NAGANUMA
2nd Author's Affiliation Hitachi Ltd. Yokohama Research Laboratory
Date 2012-09-21
Paper # ISEC2012-45
Volume (vol) vol.112
Number (no) 211
Page pp.pp.-
#Pages 8
Date of Issue