KDDI研究所と国立大学法人九州大学は、暗号解読コンテスト「TU Darmstadt Learning with Errors Challenge」において、これまで誰も解読に成功していなかった60次元のLearning with Errors問題を、世界で初めて解読した。

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

Learning with Errors問題

このため、安全性が確保される最適な次元と誤差の大きさを求めるために、多くの研究機関で高速な解法の研究が進められている。KDDI研究所と九州大学は、この度、解読アルゴリズムの高速化並びに並列化に成功し、商用クラウドの20台の仮想PCを利用することで、スーパーコンピューターを用いた総当たり方式による計算では一万年以上かかる60次元のLWE問題を、約16日間で解読した。また、55次元以下の問題についても、KDDI研究所、九州大学により解読できた。

Learning with Errors問題

本研究成果は、次世代公開鍵暗号として格子暗号を利用する際に、安全な次元や誤差の大きさを決めるための重要な情報となる。KDDI研究所と九州大学マス・フォア・インダストリ研究所は、引き続き解読アルゴリズムの高速化検討を進めるとともに、より高速で安全な次世代公開鍵暗号実現に向けた研究開発を推進していく。また、この研究成果は、10月11日〜13日に秋田で開催されるコンピュータセキュリティシンポジウム2016にて報告される予定だ。