国立研究開発法人情報通信研究機構（NICT）のサイバーセキュリティ研究所と公立大学法人首都大学東京の研究グループは2019年6月27日、量子コンピュータでも解読できない安全な暗号を実現するためのコンテストで世界記録を達成したと発表した。暗号の安全性の根拠となる方程式について、まだ誰にも解かれていない37という多くの変数の方程式を世界で初めて解いたとしている。
量子コンピュータでも解読が難しい暗号技術の1つが「多変数公開鍵暗号」である（図1）。連立二次多変数代数方程式は、変数の数が増えると解を得るために必要な時間が増える。これが安全性の根拠になる。多変数公開鍵暗号を安全に利用するためには、連立二次多変数代数方程式がいくつの変数まで解けるのかを評価する必要がある。
図1：多変数公開鍵暗号の概要（出典：国立研究開発法人情報通信研究機構、公立大学法人首都大学東京）拡大画像表示
連立二次多変数代数方程式を解くコンテスト「Fukuoka MQ Challenge」では、6タイプ（Type I～VI）の方程式が設定されている。各タイプにおいて、解かれた最大の変数の個数が報告されている。今回、NICTと首都大学東京は、Type IIとType IIIの方程式において、これまで誰も解いたことのない37個の変数の方程式を解き、3年近く更新されていなかった記録を更新した（図2）。
図2：Fukuoka MQ Challenge Type II、Type IIIの成果（出典：国立研究開発法人情報通信研究機構、公立大学法人首都大学東京）拡大画像表示
記録を更新できたポイントは、Type IIとType IIIの連立二次多変数代数方程式に特化したアルゴリズムとプログラムを開発したことにある。このアルゴリズムとプログラムは、これまでよりも計算が約5倍速く、メモリー使用量を最良の場合では8分の1に節約できる。
37変数の問題を解くためには、MQ Challengeの資料を参考にすると、23変数の問題を解く場合の約15万倍の時間がかかる。汎用ソフトを使用した場合は解読に4～16年はかかる。しかし、開発したアルゴリズムとプログラムを汎用サーバー（Xeon E5-4669 v4×4基、メモリー:1TB）で実行させたところ、Type IIの37変数については75.7日、Type IIIの37変数については56.1日で解いた。
利用したアルゴリズムでは、多項式の割り算を大量に行う。しかし、不要な割り算を実行してしまうケースが多く存在する。このため、不要な割り算をしないための判定法を開発し、計算の回数を削減した。
