KDDI研究所と九州大学は、世界中の暗号研究者の参加が見込まれる暗号解読コンテスト(ドイツ・ダルムシュタッド工科大学主催)において、これまで誰も解読できなかった60次元のLearning with Errors(LWE)問題を、世界で初めて解読したと発表した。

 金融分野などでは取引の安全性のためにネットワーク上で暗号を用いている。公開鍵暗号と呼ぶ方式では、数学的に関連付けられた2種の鍵(公開鍵と秘密鍵)を利用して情報のやり取りを行う。しかし、いずれ量子コンピュータの実現で解読されるとの懸念から難度の高い「格子暗号」という公開鍵暗号が検討されている。

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

 今回研究グループは、解読アルゴリズムの高速化と並列化に成功し、商用クラウドの20台の仮想PCを利用することで、スーパーコンピュータを用いた総当たり方式による計算では一万年以上かかる60次元のLWE問題を、約16日間で解読した。また、55次元以下の問題も解読したという。

 今回の成果は、次世代公開鍵暗号として格子暗号を利用する際に、安全な次元や誤差の大きさを決めるための重要な情報となる。今後、解読アルゴリズムの高速化検討をさらに進め、高速で安全な次世代公開鍵暗号を実現したいとしている。

九州大学

未来を切り拓く「総合知」を生み出し、社会変革を牽引する大学

今年111周年を迎えた九州大学は、12学部19学府を擁する基幹総合大学。世界最高水準の卓越した教育研究活動を展開し国際的な拠点となり得る「指定国立大学法人」として指定を受けました。これまで培い蓄積した人文社会学系から自然科学系、さらにはデザイン系の「知」を組み[…]

大学ジャーナルオンライン編集部

大学ジャーナルオンライン編集部です。
大学や教育に対する知見・関心の高い編集スタッフにより記事執筆しています。