東大が暗号解読の世界記録。従来より約47,000倍難しい問題を突破

　東京大学大学院情報理工学系研究科の坂田康亮特任研究員と高木剛教授は7月22日、次世代暗号の安全性評価に関わる「MQ問題」を高速に解くアルゴリズムで、2023年に取り組んだ問題より約47,000倍難しい問題を解読したと発表した。

　耐量子計算機暗号(ポスト量子暗号)の1つに「多変数多項式暗号」という方式があり、その解読がMQ問題だ。MQ問題を解く標準的な手法はグレブナ基底を計算するアルゴリズムである「F4」だが、計算途中に巨大な行列が現れることが大きな課題とされていた。

　2023年の研究では、ヒルベルト級数と呼ばれる数理的な道具を用いて、計算に本当に必要な組み合わせを見極めることで行列を小さくする手法を提案し、それまで解読されていなかったもっとも難しいレベルの問題の解読に約9時間で成功していた。

　今回の発表はこの延長線にあたり、計算の前半ではヒルベルト級数に基づいて必要な組み合わせを選び、後半では行列が大きくなりにくい組み合わせを優先的に選ぶことで、計算の最初から最後まで扱う行列を小さく保つことに成功した。

　MQ問題の解読性能を競うFukuoka MQ Challengeにおいて新記録を達成した(Type VI, m=24)。これは従来と比較して計算困難性が約47,000倍高いと見積もられ、次世代暗号の安全性評価に関わる計算技術を大きく前進させる成果であるという。

　今後は提案アルゴリズムの適用範囲をさらに詳しく調べるとともに、新しいCPU命令や並列計算環境を活用した高速化を進め、多変数多項式暗号を含むポスト量子暗号の安全性をより精密に評価し、将来の安全な情報通信基盤の設計に貢献するとしている。