BKZ 2.0アルゴリズムの実装と改良
スポンサーリンク
概要
- 論文の詳細を見る
格子理論の暗号分野への応用は多岐に亘る.特に,最短・最近ベクトル問題の困難性は格子暗号の安全性の根拠となっているため,これらの問題の現実的な難しさを評価することは重要である.現在高次元格子の最短ベクトル問題の近似アルゴリズムとして最も有効なものは,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ビットセキュリティであることがわかった
- 一般社団法人電子情報通信学会の論文
- 2012-09-14