| 講演名 | 2012-09-21 BKZ 2.0アルゴリズムの実装と改良 青野 良範, 長沼 健, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 格子理論の暗号分野への応用は多岐に亘る.特に,最短・最近ベクトル問題の困難性は格子暗号の安全性の根拠となっているため,これらの問題の現実的な難しさを評価することは重要である.現在高次元格子の最短ベクトル問題の近似アルゴリズムとして最も有効なものは,2011年AsiacryptでChen-Nguyenにより提案されたBKZ 2.0アルゴリズムである.彼らはTU Darmstadt lattice challengeにおいて525から800の全ての次元で新記録を達成し,同時に様々な暗号方式のセキュリティパラメータの見直しを行った.我々は,彼らのアルゴリズムにはいくつかの未知の部分と改良できる点があると考え,それを追求するためにNTLライブラリを用いた実装および実験的な改良を行った.提案したアルゴリズムは彼らのものと比較して5倍程度高速であることが確認でき,Lattice Challengeの500から675次元の問題で新記録を達成した.また,実験からHermite factor=1.01の達成に必要なCPU時問は1週間程度であり,ブロック暗号換算で42.25ビットセキュリティであることがわかった |
| 抄録(英) | 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. |
| キーワード(和) | 格子基底簡約アルゴリズム / BKZ簡約アルゴリズム / BKZ 2.0 / Lattice Challenge |
| キーワード(英) | Lattice basis reduction / BKZ reduction algorithm / BKZ 2.0 / Lattice Challenge |
| 資料番号 | ISEC2012-45 |
| 発行日 |
| 研究会情報 | |
| 研究会 | ISEC |
|---|---|
| 開催期間 | 2012/9/14(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information Security (ISEC) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | BKZ 2.0アルゴリズムの実装と改良 |
| サブタイトル（和） | |
| タイトル（英） | Heuristic improvements of BKZ 2.0 |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 格子基底簡約アルゴリズム / Lattice basis reduction |
| キーワード(2)（和/英） | BKZ簡約アルゴリズム / BKZ reduction algorithm |
| キーワード(3)（和/英） | BKZ 2.0 / BKZ 2.0 |
| キーワード(4)（和/英） | Lattice Challenge / Lattice Challenge |
| 第 1 著者 氏名（和/英） | 青野 良範 / Yoshinori AONO |
| 第 1 著者 所属（和/英） | 情報通信研究機構 National Institute of Information and Communications Technology |
| 第 2 著者 氏名（和/英） | 長沼 健 / Ken NAGANUMA |
| 第 2 著者 所属（和/英） | 日立製作所横浜研究所 Hitachi Ltd. Yokohama Research Laboratory |
| 発表年月日 | 2012-09-21 |
| 資料番号 | ISEC2012-45 |
| 巻番号（vol） | vol.112 |
| 号番号（no） | 211 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |