Laser Focus World JAPAN　レーザーフォーカスワールドジャパン

January 22, 2013, 東京--情報通信研究機構（NICT）は、暗号化したままデータを処理する技術である「完全準同型暗号」の安全性を支える「格子の最短ベクトル問題」の解析を行い、世界で初めて、825次元もの高い次元の問題を解くことに成功した。 「完全準同型暗号」を安全に利用するためには、「格子の最短ベクトル問題」がどの次元まで解けるのかを評価することが必要となる。
NICTと株式会社日立製作所は共同で、「格子の最短ベクトル問題」の難しさの評価を行った。両機関はこの問題を解くために、現在知られている最も効率の良いアルゴリズムに改良を加え、パラメータを最適化したプログラムを開発した。
この改良プログラムを実証するため、ドイツのダルムシュタット工科大学が主催し、世界の著名な暗号研究者がしのぎを削っている解読コンテスト「TU Darmstadt Lattice Challenge」に挑戦。その結果、これまで1年以上更新がなされていなかった世界記録を更新し、825次元の格子の最短ベクトル問題を、市販の汎用サーバ(CPU: AMD Opteron 6276 (2.3GHz/16Core)×4, メモリ: 64GB)を用いて、わずか5.5日で解くことに成功した。
「完全準同型暗号」を利用すると、他へ機密データの内容を一切知らせることなく計算作業を託すことが可能となるなど、クラウド・コンピューティング等でのセキュリティ確保のためにこの暗号が活用されることが期待されている。「格子の最短ベクトル問題」の評価は、完全準同型暗号を安全に利用するために不可欠であり、実用化に向けた第一歩となる。
格子の最短ベクトル問題についてNICTと日立製作所は、「難しい問題であるが、BKZアルゴリズムと呼ばれる、問題を少しずつ簡単なものに変換していくタイプのアルゴリズムを何回か繰り返すと、最終的に最短ベクトルを計算することができる。我々は、パラメータの最適化や無駄な処理の削減により、この変換処理を高速化した。また、（近似）最短ベクトル問題を解くための、具体的な計算時間を予測する手法を開発した」と説明している。
(詳細は、www.nict.go.jp)