「格子の最短ベクトル問題」の解析において世界で初めて“825次元”の問題を5.5日で解くことに成功(NICT、日立)

製品・サービス・業界動向新製品・新サービス

2013年1月22日（火） 08時00分

　情報通信研究機構（NICT）と日立製作所は21日、「格子の最短ベクトル問題」の解析において、世界で初めて、“825次元”の問題を5.5日で解くことに成功したことを発表した。

　「格子の最短ベクトル問題」は、現在広く利用されている公開鍵暗号の安全性評価に活用されている他、量子コンピュータ実現後も高い安全性が保たれる「格子暗号」の安全性の根拠となっている問題。そのため、「格子暗号」を発展させた「完全準同型暗号」を安全に利用するために、不可欠なバックボーンとされている。

　「完全準同型暗号」は、2009年に米IBM社から発表され、データを暗号化したままさまざまな演算が可能となる技術。完全準同型暗号を利用すると、他へ機密データの内容をいっさい知らせることなく計算作業を託すことが可能となるため、クラウド・コンピューティング等でのセキュリティ確保に期待が寄せられており、世界の多くの機関が研究を進めている。

　NICTと日立製作所は共同で、アルゴリズムに改良を加え、パラメータを最適化したプログラムを開発。ドイツのダルムシュタット工科大学が主催する解読コンテスト「TU Darmstadt Lattice Challenge」に挑戦し、これまで1年以上更新されていなかった世界記録を更新した。825次元の格子の最短ベクトル問題を、市販の汎用サーバ（CPU: AMD Opteron 6276（2.3GHz/16Core）×4、メモリ: 64GB）を用いて、5.5日で解くことに成功したという。

NICTと日立、クラウド向け暗号技術で世界新記録を達成……“825次元”の格子問題

《冨岡晶@RBB TODAY》