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 |