ニュース
東大、これまでに解かれたことのない次元の暗号解読を実現
2023年10月25日 12:38
東京大学大学院 情報理科工学系研究科の坂田康亮特任研究員と高木剛教授は、量子コンピュータも解読できないほどのポスト量子暗号において、暗号解読のためのアルゴリズムを考案し、次世代暗号解読コンテストである「MQチャレンジ」において「これまでに解かれたことがない次元の暗号解読」の世界記録を達成したという。
現代的な暗号化手法は、量子コンピュータが実用レベルに達すると簡単に解読されることが知られている。そこで米国標準技術研究所(NIST)は、量子コンピュータでも解読が困難で安全な耐量子計算機暗号の選定を進めている。その中での安全性を保証するために、攻撃者の計算限界を解明することを目標に、もっとも効率的な攻撃アルゴリズムを評価する研究も進められている。
耐量子計算機暗号の1つに「多変数多項式暗号」という方式があり、その解読問題は連立二次多変数多項式の求解問題(MQ問題)である。そしてこの問題の困難性を評価するための解読コンテストが「MQチャレンジ」だ。今回の研究では、このMQチャレンジの中で、これまでに解読されていないもっとも難しいレベルの問題(Type VI、次元31、方程式数21)の解読を約9時間で成功した。
具体的には、MQ問題を解く標準的な手法は、グレブナ基底を計算するアルゴリズムである「F4」を用いるが、その解読には巨大な行列を計算する必要があった。そこで、MQ問題が持つ数理的特性をヒルベルト級数により解明し、計算する多項式の数を最小化するアルゴリズムを構築。F4が生成する行列の中から、計算に本質的な領域のみを取り出した小さな行列を計算することで、高速化を実現したという。
今後、新しいアルゴリズムを詳細に評価することで、現在進められている次世代暗号の標準化規格に対して安全なパラメータの提案を行なうとしている。
