KDDI研究所と九大、６０次元のLearning　with　Errors問題の解読に成功

〜スーパーコンピューターでも一万年以上かかる問題を、約１６日間で解読に成功！〜
世界で誰にも解読されていない暗号問題を初めて解読！


　株式会社KDDI研究所（本社：埼玉県ふじみ野市、代表取締役所長：中島康之、以下「KDDI研究所」）と国立大学法人九州大学（本部：福岡市西区、総長　久保千春、以下「九州大学」）は、暗号解読コンテスト「TU　Darmstadt　Learning　with　Errors　Challenge（注１）」において、これまで誰も解読に成功していなかった６０次元のLearning　with　Errors（以下、LWE）問題を、世界で初めて（注２）解読しました。

　LWE問題は、故意に誤差を付加した多元連立一次方程式を解く問題です。この問題を解くことは、多くの研究機関で研究が進められている格子暗号（注３）が解読できることに相当します。安全な暗号を実現するためには、LWE問題の次元（未知変数の個数）を高め、または誤差を大きくし、解読を困難にする必要があります。しかし、次元が高すぎると計算時間が増大し、誤差が大きすぎると正しい暗号処理が行えない確率が増大します。
このため、安全性が確保される最適な次元と誤差の大きさを求めるために、多くの研究機関で高速な解法の研究が進められています。

　KDDI研究所と九州大学は、この度、解読アルゴリズムの高速化並びに並列化に成功し、商用クラウドの２０台の仮想PCを利用することで、スーパーコンピューターを用いた総当たり方式による計算では一万年以上かかる（注４）６０次元のLWE問題を、約１６日間で解読しました。また、５５次元以下の問題についても、KDDI研究所、九州大学により解読できました。

　本研究成果は、次世代公開鍵暗号（注５）として格子暗号を利用する際に、安全な次元や誤差の大きさを決めるための重要な情報となります。

　KDDI研究所と九州大学マス・フォア・インダストリ研究所は、引き続き解読アルゴリズムの高速化検討を進めるとともに、より高速で安全な次世代公開鍵暗号実現に向けた研究開発を推進していきます。また、本研究成果は、２０１６年１０月１１日〜１３日に秋田で開催されるコンピュータセキュリティシンポジウム２０１６にて報告予定です。

　（注１）TU　Darmstadt　Learning　with　Errors　Challengeはドイツのダルムシュタッド工科大学が主催するコンテスト。暗号解読をめぐって、世界中の暗号研究者の参加が見込まれる。
　https://www.latticechallenge.org/lwe_challenge/challenge.php

　（注２）２０１６年７月１９日時点。

　（注３）格子暗号とは、LWE問題や格子の最短ベクトル問題などを安全性の根拠とする公開鍵暗号方式。次世代公開鍵暗号の有力な候補の一つで、現在使われているRSA暗号や楕円曲線暗号よりも安全かつ高速な方式として期待されている。格子暗号を用いると、暗号文の状態で様々な演算が可能になる完全準同型暗号など実用的な暗号システムを構成することができるため、多くの研究機関で研究が進められている。

　（注４）解読アルゴリズムを利用せず、解となりうる全ての可能性を、２０１６年時点における世界最高性能のスーパーコンピューターで試した場合。

　（注５）公開鍵暗号とは二つの鍵（AとA"）を作成し、どちらか一方の鍵で暗号化し、もう一方で復号するという仕組み。自分あてに情報を送るための暗号化用の鍵（A）は世間に広く公開しておき（公開鍵）、その鍵（A）を使って暗号化して送ってもらう。復号するためには、公開してある鍵ではないもう一方の鍵（A’）で復号する。この復号するための鍵（秘密鍵）は復号する本人しか知らないので、復号できるのは本人のみとなる。この二つの鍵は、数学的な関係があるので、関係のない他の鍵で復号することはできない。RSA暗号や楕円曲線暗号等が主流となっており、オンライン決済やSSLの暗号化通信といった、個人情報のやり取りなどに使われている。

　※別紙は添付の関連資料を参照