LWE問題の概要
KDDI研究所は7月19日、世界でいまだ誰にも解読されておらず、スーパーコンピューターでも1万年かかるという暗号の解読に成功したと発表した。
KDDI研究所と九州大学によるもので、ドイツのダルムシュタッド工科大学で開催される暗号解読コンテスト「TU Darmstadt Learning with Errors Challenge 」において、これで誰も解読に成功していなかった60次元LWE（Learning with Errors）問題の解読に成功したというもの。
LWE問題は、故意に誤差を負荷した多元連立1次方程式を解くもので、次元（未知変数の個数）が大きくなると計算時間が膨大となり、誤差が大きいと解読できなくなる可能性があることから、暗号として用いる際には次元と誤差の量をどの程度にするのかがポイントとなる。LWE問題は60次元の計算ともなると、スーパーコンピューターを用いた総当り計算では1万年以上かかるが、KDDI研究所と九州大学ではアルゴリズムを工夫して解を導かない計算を排除する効率的な解読処理を考案。20台の仮想PCの並列処理により約16日で解読に成功した。
解読処理の概要
LWE問題が解読できるということは、次世代の公開鍵暗号の基本暗号技術となる格子暗号も解く手法があることになる。このため、今回のLWE暗号の解読は、将来的に公開鍵暗号として格子暗号を利用する際に安全な次元や誤差の量を決定するための重要な要素となるという。
