NICTなど、825次元の格子の最短ベクトル問題を5.5日で解くことに成功

情報通信研究機構(NICT)は1月21日、暗号化したままデータを処理する技術「完全準同型暗号(Fully Homomorphic Encryption)」の安全性を支える「格子の最短ベクトル問題」の解析を行い、825次元という高次元の問題を解くことに成功したと発表した。同成果の詳細は2013年1月22日～25日に京都で開催される「2013年 暗号と情報セキュリティシンポジウム(SCIS2013)」で発表される。

クラウド・コンピューティングの発展により、従来は組織内サーバで行っていた情報処理を、外部の計算機資源で行う流れが進み、機密データについても安心してクラウドを活用できる技術が求められるようになっている。"完全準同型暗号"は2009年にIBM社が発表した暗号化技術で、格子理論を利用し、データを暗号化したまま さまざまな演算が可能となる技術として注目を集めている。この暗号技術の安全性を支える根拠の1つが、"格子の最短ベクトル問題"と呼ばれる難問で、現在広く利用されている公開鍵暗号の安全性評価にも活用されているほか、量子コンピュータ実現後も高い安全性が保たれる格子暗号の安全性の根拠となっており、"完全準同型暗号"を安全に利用するためには、この"格子の最短ベクトル問題"がどの次元まで解けるのかを評価することが必要となるあめ、極めて重要な問題として世界各地の研究機関で研究が進められている。

一般的な格子暗号は、例えば、メッセージ送信者が受信者に対して、1文字のひらがなを送る場合を考えた場合、まず、メッセージの送信者が受信者に対して、格子暗号で文字を送ることを伝える。次にメッセージの受信者は格子模様を用意し、交点に文字を書き込み、それを斜め上から写真に撮ったものをメッセージ送信者に送る。その写真を受け取ったメッセージ送信者は、自分が送りたい文字の近くに印を付けて、受信者に送り返す。この際、その印が、文字を暗号化したものとなるが、印と文字が近過ぎる場合、写真を盗み見た人にメッセージが分かってしまうため、適度に離しておく必要がある。そして最後に、返信された写真の印を手元の格子模様に写して見比べ、印に一番近い交点の文字を読むことで、メッセージを読み取ることが可能となる。

ただし、この場合、写真を盗み見た第3者が格子の最短ベクトル問題を解くことができれば、写真に付けられた印の位置からもとの文字を読み取れることができることが知られている。そのため、この問題の難しさを評価し、例え写真を盗み見られても安全であるようなパラメータを見積もることが必要になっていた。

格子暗号では文字だけでなく数字も同様の原理で送ることが可能だが、完全準同型暗号方式を用いることで、数字同士を暗号化したまま加算と乗算を行うことが可能となる。例えば、数字の"1"を暗号化した印(赤い＊)と数字の"3"を暗号化した印(青い＊)を足すことで、新しい印(緑の＊)ができる。これを格子暗号と同様、復元すると数字の"4"が出てくることとなる。印同士の乗算を考えることで、数字を暗号化したままで乗算をすることもできる。

今回、NICTと日立製作所の研究グループは、"格子の最短ベクトル問題"の難しさの評価を行うために、現在知られている高効率アルゴリズム「BKZアルゴリズム」に改良を加え、パラメータを最適化することで変換処理を高速化したプログラムを開発。また、(近似)最短ベクトル問題を解くための具体的な計算時間を予測する手法も開発し、この改良プログラムの実証のため、独ダルムシュタット工科大学が主催している、格子の最短ベクトル問題のコンテストである「TU Darmstadt Lattice Challenge」に挑戦。その結果、これまで1年以上更新がなされていなかった世界記録を更新し、825次元の格子の最短ベクトル問題を、市販の汎用サーバ(CPU:AMD Opteron 6276(2.3GHz/16Core)×4、メモリ:64GB)を用いて、5.5日で解くことに成功したという。

なお、研究グループではクラウド上での秘匿情報処理の実用化に向け、より高速な解読アルゴリズムを開発し、さらに大規模な実験により安全性を検証していく方針としている。