日時： 2015年11月25日(水) 17:00–18:00
場所： 東京大学工学部 6号館 2階 63号講義室
http://www.u-tokyo.ac.jp/campusmap/cam01_04_07_j.html
講演者： 高木 剛（九州大学IMI）
題目： 公開鍵暗号の安全性評価
概要：
暗号解読技術は数学をベースに年々進歩し続けており，
暗号は危殆化リスクを常に抱えている状況にある．
1980年代からは最先端の数学理論を用いた暗号解読
アルゴリズム(数体篩法,楕円曲線法など)が進展してきた．
1994年にはShorが量子計算機により素因数分解問題と
離散対数問題の量子多項式時間アルゴリズムを発表し，
現在普及している暗号(RSA暗号,楕円曲線暗号など)は
危殆化する状況にある．そのため，格子最短ベクトル
問題(SVP)，多変数多項式求解問題(MQ問題)，楕円曲線
同種写像問題(Isogeny問題)などの数学問題の困難性に
基づく暗号(Post-Quantum Cryptography)の研究が進ん
でいる．
本講演では，SVPの困難性に基づく公開鍵暗号に関する
研究動向を紹介する．SVPを効率的に解く計算法として，
格子基底縮約法(LLL,BKZ)，列挙法(Extreme pruning)，
篩法(Gauss sieve)などが知られている．これらのアル
ゴリズムの概要を述べた後に，ドイツ・ダルムシュタット
工科大学が主催するSVP Challengeの解読世界記録を
紹介する．SVP Challengeの解読データにより，攻撃者
の計算限界を評価することができ，格子理論ベースの
公開鍵暗号で用いる安全なパラメータを構成すること
が可能となる．