東京大学(東大)は10月23日、次世代暗号の解読コンテストである「MQチャレンジ」において、これまでに解読されたことがない最も難しいレベルである問題TypeVI、次元31、方程式数21の解読に約9時間で成功したことを発表した。
同成果は、東大大学院 情報理工学系研究科の坂田康亮特任研究員、同・高木剛教授らの研究チームによるもの。詳細は、10月30日から11月2日に福岡の会場とオンラインでハイブリッド開催される予定の情報処理学会主催のコンピュータセキュリティシンポジウム「CSS 2023」にて発表される予定だ。
-
今回提案されたアルゴリズムのイメージ(出所:東大プレスリリースPDF)
現在使用されている暗号技術は、量子コンピュータが実用的なレベルに達すると解読できるようになってしまうため、現在、米国標準技術研究所(NIST)がそれに対応するための「耐量子計算機暗号」の選定を進めている最中だ。また、耐量子計算機暗号の安全性を保障するため、攻撃者の計算限界を解明することを目標に、最も効率的な攻撃アルゴリズムを評価する研究も同時に進められている。
暗号の解読問題の難度を横軸に、攻撃アルゴリズムの計算量を縦軸に取ってグラフ化すると、暗号パラメータを大きくすることで解読問題の難度を上げることができるのがわかる。そこで攻撃手法の研究が進み、最も効率的な攻撃アルゴリズムがより強力になると解読問題の難度は下がり、攻撃者の手で解読されてしまう危険性が生じる。このような状況は「暗号の危殆化(きたいか)」と呼ばれ、情報漏洩などにより犯罪に悪用されることが危惧されている。暗号の危殆化を回避するためには、想定されうる最も効率的な攻撃アルゴリズムを解明し、その攻撃アルゴリズムを基に暗号パラメータを決定する必要があるとする。
-
解読問題の難度と問題の計算量の関係(出所:東大プレスリリースPDF)
耐量子計算機暗号の1つに、「多変数多項式暗号」という暗号方式がある。その解読問題は、連立二次多変数多項式の求解問題である「MQ問題」だ。そのMQ問題の困難性を評価するために実施されているのが、解読コンテスト「MQチャレンジ」であり、研究チームは同コンテストに参加することにし、これまでに解読されていない最も難しいレベルである問題TypeVI、次元31、方程式数21の解読に約9時間で成功したという。
-
次元10のF4(従来)と提案されたアルゴリズムの比較(出所:東大プレスリリースPDF)
MQ問題を解く標準的な手法としては、多変数の連立方程式を解く時などに使用される幅広い応用を持つことで知られる「グレブナ基底」を計算する標準的なアルゴリズムである「F4」が知られている。ただし、解読には巨大な行列を計算する必要があった。
そこで今回の研究では、MQ問題が持つ数理的特性を、多変数多項式の集合に対して定義できる一変数の級数であり、その集合の代数構造の情報を持つ「ヒルベルト級数」により解明し、計算する多項式の数を最小化するアルゴリズムの構築が行われた。その結果、F4が生成する行列の中から、計算に本質的な領域のみを取り出した小さな行列を計算することで高速化に成功したという。実際、計算する行列を小さくしても、グレブナ基底計算の観点ではまったく同等な結果となっているとした。
現在、NISTでは次世代デジタル署名暗号の標準化の選定が進められており、主要な候補の中に多変数多項式暗号がある。今回解読に成功した問題の種類は、多変数多項式暗号によるデジタル署名に現れるMQ問題と一致する。研究チームは今後、この新しいアルゴリズムを詳細に評価することで、現在進められている次世代暗号の標準化規格に対して安全なパラメータの提案を進めるとしている。
