KDDI研究所と九州大学は、世界中の暗号研究者の参加が見込まれる暗号解読コンテスト（ドイツ・ダルムシュタッド工科大学主催）において、これまで誰も解読できなかった60次元のLearning with Errors（LWE）問題を、世界で初めて解読したと発表した。
金融分野などでは取引の安全性のためにネットワーク上で暗号を用いている。公開鍵暗号と呼ぶ方式では、数学的に関連付けられた2種の鍵（公開鍵と秘密鍵）を利用して情報のやり取りを行う。しかし、いずれ量子コンピュータの実現で解読されるとの懸念から難度の高い「格子暗号」という公開鍵暗号が検討されている。
LWE問題は、故意に誤差を付加した多元連立一次方程式を解く問題。これは格子暗号の解読に相当するという。安全な暗号の実現には、LWE問題の次元（未知変数の個数）を高め、または誤差を大きくし、解読を困難にする必要がある。しかし、次元が高すぎると計算時間が増大し、誤差が大きすぎると正しい暗号処理が行えない確率が増大する。このため、安全性が確保される最適な次元と誤差の大きさを求めるために、多くの研究機関で高速な解法の研究が進められている。
今回研究グループは、解読アルゴリズムの高速化と並列化に成功し、商用クラウドの20台の仮想PCを利用することで、スーパーコンピュータを用いた総当たり方式による計算では一万年以上かかる60次元のLWE問題を、約16日間で解読した。また、55次元以下の問題も解読したという。
今回の成果は、次世代公開鍵暗号として格子暗号を利用する際に、安全な次元や誤差の大きさを決めるための重要な情報となる。今後、解読アルゴリズムの高速化検討をさらに進め、高速で安全な次世代公開鍵暗号を実現したいとしている。
