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

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

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

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

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

九州大学
九州大学

日本の様々な分野において指導的な役割を果たし、広く全世界で活躍する人材を輩出し、日本及び世界の発展に貢献する

「基幹教育」と「専攻教育」から成立する学部教育。生涯にわたって学び続けることを幹に持ち、行動力を備えたアクティブ・ラーナーへと育つ力を培います。深い専門性や豊かな教養へとつながる知識・技能と、新たな知や技能を創出し未知な問題を解決するもとである「ものの見方・考[…]

この記事が気に入ったらおねがいします。

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

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

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