| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2012-09-21 10:10 BKZ2.0アルゴリズムの実装と改良 ○青野良範（NICT）・長沼 健（日立）  ISEC2012-45 |
|
| 抄録 | （和） | 格子理論の暗号分野への応用は多岐に亘る． 特に，最短・最近ベクトル問題の困難性は格子暗号の安全性の根拠となっているため， これらの問題の現実的な難しさを評価することは重要である． 現在高次元格子の最短ベクトル問題の近似アルゴリズムとして最も有効なものは， 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 (closest) 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 / / / / | |
| 文献情報 | 信学技報, vol. 112, no. 211, ISEC2012-45, pp. 15-22, 2012年9月. | |
| 資料番号 | ISEC2012-45 | |
| 発行日 | 2012-09-14 (ISEC) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | ISEC2012-45 |
|
| 研究会情報 | |
| 研究会 | ISEC |
| 開催期間 | 2012-09-21 - 2012-09-21 |
| 開催地（和） | 機械振興会館 |
| 開催地（英） | Kikai-Shinko-Kaikan Bldg. |
| テーマ（和） | 一般 |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | ISEC |
| 会議コード | 2012-09-ISEC |
| 本文の言語 | 日本語 |
| タイトル（和） | BKZ2.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 |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 青野 良範 / Yoshinori Aono / アオノ ヨシノリ |
| 第1著者 所属（和/英） | 情報通信研究機構 (略称： NICT) National Institute of Information and Communications Technology (略称： NICT) |
| 第2著者 氏名（和/英/ヨミ） | 長沼 健 / Ken Naganuma / |
| 第2著者 所属（和/英） | 日立製作所 横浜研究所 (略称： 日立) Hitachi, Ltd., Yokohama Research Laboratory (略称： Hitachi) |
| 第3著者 氏名（和/英/ヨミ） | / / |
| 第3著者 所属（和/英） | (略称： ) (略称： ) |
| 第4著者 氏名（和/英/ヨミ） | / / |
| 第4著者 所属（和/英） | (略称： ) (略称： ) |
| 第5著者 氏名（和/英/ヨミ） | / / |
| 第5著者 所属（和/英） | (略称： ) (略称： ) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 第7著者 氏名（和/英/ヨミ） | / / |
| 第7著者 所属（和/英） | (略称： ) (略称： ) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2012-09-21 10:10:00 |
| 発表時間 | 25分 |
| 申込先研究会 | ISEC |
| 資料番号 | ISEC2012-45 |
| 巻番号（vol） | vol.112 |
| 号番号（no） | no.211 |
| ページ範囲 | pp.15-22 |
| ページ数 | 8 |
| 発行日 | 2012-09-14 (ISEC) |
[研究会発表申込システムのトップページに戻る]