【計算機科学】世界で誰にも解読されていない暗号問題を初めて解読！
http://potato.2ch.net/test/read.cgi/scienceplus/1468931086/
世界で誰にも解読されていない暗号問題を初めて解読！ | 株式会社KDDI研究所
http://www.kddilabs.jp/newsrelease/2016/071901.html
http://www.kddilabs.jp/newsrelease/2016/071901a.html
http://www.kddilabs.jp/sites/default/files/newsrelease/JA-img/20160719_02.jpg
株式会社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）として格子暗号を利用する際に、安全な次元や誤差の大きさを決めるための重要な情報となります。
