KDDI研究所と九州大学(九大)は、暗号解読コンテスト「TU Darmstadt Learning with Errors Challenge」において、これまで誰も解読に成功していなかった60次元のLearning with Errors(LWE)問題を解読したと発表した。
同成果は、2016年10月11日～13日に秋田で開催される「コンピュータセキュリティシンポジウム2016」で発表される予定。
LWE問題は、故意に誤差を付加した多元連立一次方程式を解く問題で、同問題を解くことは、次世代公開鍵暗号の有力な候補のひとつである格子暗号が解読できることに相当する。安全な暗号を実現するためには、LWE問題の次元(未知変数の個数)を高めるか、誤差を大きくし解読を困難にする必要があるが、次元が高すぎると計算時間が増大し、誤差が大きすぎると正しい暗号処理が行えない確率が増大するという課題がある。
今回、KDDI研究所と九州大学は、解読アルゴリズムの高速化および並列化に成功し、商用クラウドの20台の仮想PCを利用することで、スーパーコンピュータを用いた総当たり方式による計算では1万年以上かかる60次元のLWE問題を、約16日間で解読。55次元以下の問題についても解読できたという。
KDDI研究所は今回の成果について、「次世代公開鍵暗号として格子暗号を利用する際に、安全な次元や誤差の大きさを決めるための重要な情報となる」と説明している。
|
LWE問題の概要 |
