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

世界で誰にも解読されていない暗号問題を

初めて解読！

～スーパーコンピューターでも

　一万年以上かかる問題を、約16日間で

　解読に成功！～

2016/7/29　日本の研究.com

詳細は、リンクを参照して下さい。

---------------------------------------

　株式会社KDDI研究所(以下「KDDI研究所」)

と国立大学法人九州大学(以下「九州大学」)

は、暗号解読コンテスト

「TU Darmstadt Learning with Errors

　Challenge (注1)」において、

これまで誰も解読に成功していなかった

60次元のLearning with Errors

(以下、LWE)問題を、世界で初めて

(注2)解読しました。

　LWE問題は、故意に誤差を付加した

多元連立一次方程式を解く問題です。

　この問題を解くことは、

多くの研究機関で研究が進められている

格子暗号(注3)が解読できることに

相当します。

　安全な暗号を実現するためには、

LWE問題の次元(未知変数の個数)を高め、

または誤差を大きくし、解読を困難にする

必要があります。

　しかし、次元が高すぎると計算時間が

増大し、誤差が大きすぎると

正しい暗号処理が行えない確率が

増大します。

　このため、安全性が確保される

最適な次元と誤差の大きさを求めるために、

多くの研究機関で高速な解法の研究が

進められています。

　KDDI研究所と九州大学は、

この度、解読アルゴリズムの高速化

並びに並列化に成功し、商用クラウドの

20台の仮想PCを利用することで、

スーパーコンピューターを用いた

総当たり方式による計算では

一万年以上かかる(注4)60次元の

LWE問題を、約16日間で解読しました。

　また、55次元以下の問題についても、

KDDI研究所、九州大学により

解読できました。

　本研究成果は、次世代公開鍵暗号(注5)と

して格子暗号を利用する際に、

安全な次元や誤差の大きさを決めるための

重要な情報となります。

　KDDI研究所と九州大学

マス・フォア・インダストリ研究所は、

引き続き解読アルゴリズムの高速化検討を

進めるとともに、より高速で安全な

次世代公開鍵暗号実現に向けた研究開発を

推進していきます。

　また、本研究成果は、2016年10月11日

～13日に秋田で開催される

コンピュータセキュリティシンポジウム

2016にて報告予定です。

---------------------------------------

　暗号ね～

　暗号は安全だと思っていても、進化

しているので油断できませんね。