東京大学大学院情報理工学系研究科の坂田康亮特任研究員と高木剛教授は、次世代暗号の安全性評価に関わるMQ問題を高速に解く新しいアルゴリズムを開発した。MQ問題は多変数の二次方程式を同時に解く問題であり、量子コンピュータでも解読が難しいとされるポスト量子暗号の安全性評価に用いられる。従来の解読手法では計算途中に巨大な行列が現れることが課題であった。
本研究では、ヒルベルト級数を用いて計算に必要な組合せを見極め、計算過程全体で行列を小さく保つ手法を提案し、従来記録より約47,000倍難しいとされるMQ問題の解読に成功した。本成果は国際会議CHES2026に採択され、英国夏時間2026年7月17日付で「TCHES2026」に掲載された。
From: 
次世代暗号の「解読の限界」に挑む新アルゴリズムを開発～従来より約47,000倍難しいMQ問題を解読し、世界記録を達成～
【編集部解説】
「暗号の解読記録を更新」と聞くと、私たちの通信やデータが危うくなったのかと身構えたくなります。けれど今回の東京大学の成果は、その直感とは逆の意味を持っています。これは「暗号を破った」ニュースではなく、「暗号の強さを、これまでより正確に測れるようになった」ニュースです。
まず、舞台となっているMQ問題について。これは多変数の二次方程式を一度に満たす答えを探す問題です。量子コンピュータでも効率的に解く一般的な方法は知られておらず、多変数暗号と呼ばれる次世代暗号の一族が、この「解きにくさ」そのものを安全性の土台に据えています。MQ問題の難しさは、変数の数、式の数、有限体の大きさ、方程式系の構造といった要素の組み合わせで決まります。今回の舞台となったベンチマークの同じ区分では、設定される問題規模が大きくなるほど、解くために必要な計算量が急激に膨らみます。
ここで大事なのは、暗号の設計者が「この問題は現実的な時間では解けない」と言い切るためには、逆に「最先端の解読アルゴリズムでどこまで解けるのか」を知っている必要がある、という点です。攻める道具が鋭くなるほど、守る側は安全の線引きを正確に引けます。今回の研究は、この“ものさし”を一段精密にした仕事だと編集部は捉えています。
技術的な核心も、噛み砕くとシンプルです。従来の解法では、計算の途中で巨大な行列がふくらみ、メモリと時間を圧迫していました。坂田特任研究員と高木教授は、ヒルベルト級数という数学の道具を使って「本当に必要な計算だけ」を先に見極め、無駄な計算（ゼロに潰れてしまう計算）を減らすことで、行列を最後まで小さく保つ工夫を組み込みました。これにより、既存の高速ソルバーとして知られるM4GBやMagmaのF4を上回る性能を実現しています。
その結果が、MQ問題の求解性能と到達規模を競う国際的な公開ベンチマーク「Fukuoka MQ Challenge」での世界記録です。GF(31)上のType VIと呼ばれる区分で、変数36・式24（m=24）という、これまで届かなかった規模の問題を解きました。公式記録によると、この計算ではヒルベルト級数を用いたF4（HDF4）とMutant型のF4（MF4）を併用し、36変数のうち15変数を推測。各インスタンスを16スレッドで実行し、解が見つかるまでに合計2,011インスタンスを処理しています。実行には4基のAMD EPYC 7763を使い、約11日半を要しました。
プレスリリースが「従来より約47,000倍難しい」と表現しているのは、この到達点の跳躍幅を指したものです。ここで数字の意味を一つ補助線として引いておきます（以下は編集部の解釈です）。この「約47,000倍」は、Fukuoka MQ Challengeの旧記録（m=20）と今回の新記録（m=24）を、問題規模から見積もった推定計算量で比べたときの比であり、実測時間の倍率ではありません。実運用の暗号が47,000倍深く破られた、という意味でもありません。あくまで解読実験が到達した“難所の深さ”を示す数字だと読むのが正確です。
そして、なぜ今この成果に注目すべきなのか。理由は制度の側にあります。米国のNISTが進めるポスト量子暗号の追加署名標準化は、2026年5月14日に第2ラウンドを終えたところです。UOVやMAYO、SNOVA、QR-UOVといったOil and Vinegar系の多変数署名に加え、MQ問題にMPC-in-the-Headという別の設計を組み合わせたMQOMなど、MQ問題に関連する困難性を安全性の根拠とする方式が第3ラウンドへと駒を進めました。第2ラウンドでは、これら多変数系の一部パラメータが攻撃を受け、堅牢性に疑問符がついた候補もありました。それでもNISTは、UOV系の4候補については未破壊のパラメータと性能上の利点を評価し、MQOMについては性能と基盤問題の相対的な安定性を踏まえ、それぞれを次段階へ進めています。
つまり、「多変数暗号の安全パラメータをどこに設定すべきか」を世界が真剣に議論しているまさにその瞬間に、その判断材料となるMQ問題の解きやすさが更新されたわけです。標準を決める側にとって、解読の最前線がどこまで来ているかは、安全マージンを見積もるうえで無視できない判断材料になり得ます。タイミングとして、これ以上ないほど噛み合っています。
長い視点で見ると、この研究には二つの顔があります。攻撃側の道具が進化したという意味では警戒すべき側面がありますが、その進化を公開の場で明らかにし、標準化の議論に還元できるという意味では、むしろ暗号の信頼性を底上げする営みです。破られる前提を正しく知っておくことこそ、量子時代に耐える暗号を選ぶための確かな一歩だと言えます。
未来の通信の安全は、こうした「解く側」と「守る側」の終わりのない対話の上に成り立っています。今回の東京大学の一手は、その対話を一歩前へ進めた確かな記録として記憶されるはずです。
【用語解説】
MQ問題（多変数二次多項式問題）
複数の変数を含む二次方程式を、同時にすべて満たす解を見つける問題である。素朴には、有限体の大きさをq、変数の数をnとすると候補解はqのn乗まで広がるが、実際の難しさは式の数や方程式系の構造にも左右される。この「解きにくさ」が、多変数暗号など一部のポスト量子暗号の安全性の根拠に使われている。
ポスト量子暗号（PQC）
量子コンピュータが実用化しても破られにくいよう設計された暗号方式の総称である。現在広く使われるRSAや楕円曲線暗号は、大規模な量子計算で破られる恐れがあるため、その代替として世界的に整備が進んでいる。ただし、量子攻撃に対する実用上の安全性が無条件に保証されているわけではなく、既知の攻撃手法と計算困難性の仮定に基づいて評価されている。
多変数暗号（多変数公開鍵暗号）
MQ問題の難しさを安全性の土台とする暗号方式の一族である。方式によっては署名や検証が速いという利点がある一方、公開鍵が大きくなりやすく、過去にも直近の審査でも一部の方式やパラメータが攻撃を受けており、パラメータ設定の慎重さが求められている。
F4アルゴリズム／グレブナー基底
グレブナー基底は、多項式イデアルの標準的な生成系であり、連立多項式の求解や消去に用いられる。これを行列の線形代数を使って高速に計算する代表的手法がF4アルゴリズムで、MQ問題を解く際の中心的な道具となる。
ヒルベルト級数
次数ごとの構造（各次数成分の次元）を生成関数として数え上げる数学的な道具である。今回の研究では、各次数で必要となる計算量を予測し、本当に必要な計算だけを見極めるために活用された。
ゼロ簡約（ゼロ簡約の削減）
グレブナー基底の計算途中で、結果的にゼロになってしまう計算を指す。このうち事前に回避できる不要なゼロ簡約を減らすことが、計算の高速化と行列サイズの抑制につながる。
M4GB
MQ問題の求解で高い性能を示したグレブナー基底計算アルゴリズムの一つである。過去にはType VI・GF(31)で最大19式までを最長約11日以内で解き、記録を更新した。今回の新手法は、このM4GBを上回る性能を示したと報告されている。
Type VI／GF(31)
Fukuoka MQ Challengeにおける問題区分の一つで、31を法とする有限体（GF(31)）上に定義される多変数二次方程式系を指す。式の数mより変数の数nが多い劣決定系（n≈1.5m）で、署名用途を想定した解読の難しい区分である。今回の記録はn=36・m=24。
UOV／MAYO／SNOVA／QR-UOV／MQOM
いずれもMQ問題に関連する困難性に安全性の根拠を置き、NISTの追加署名標準化で第3ラウンドに進んだ署名方式である。UOV・MAYO・SNOVA・QR-UOVはUOV（Unbalanced Oil and Vinegar）を基礎とする系統。MQOMはMQ問題を用いるが、NISTの分類ではMPC-in-the-Head型に位置づけられる。
【参考リンク】
東京大学 大学院情報理工学系研究科（外部）
今回のプレスリリースを公開した東京大学の研究科公式サイト。所属研究者やプレスリリース、最新ニュースの一覧を確認できる。
Fukuoka MQ Challenge（外部）
MQ問題の解読難易度を世界中の研究者が競う国際公開ベンチマークの公式サイト。問題と歴代記録の一覧を公開している。
Fukuoka MQ Challenge：Type VI・m=24 記録詳細（外部）
今回の世界記録（n=36・m=24）の登録詳細ページ。使用アルゴリズムやハードウェア、実行時間を確認できる。
IACR TCHES（該当論文ページ）（外部）
今回の成果を掲載した査読付き学術誌TCHESの論文ページ。国際暗号学会IACRが運営し、ハードウェア暗号を扱う。
論文DOI（IACR TCHES 2026）（外部）
今回の論文の恒久リンク（DOI）。掲載巻号とページ（i3, 1284-1309）に直接たどり着き、原典を参照できる。
NIST Post-Quantum Cryptography（外部）
米国NISTによるポスト量子暗号プロジェクトの公式ページ。標準化の進捗状況や、企業・行政機関などの組織向けの移行情報をまとめている。
NIST Round 3 Additional Signatures（候補一覧）（外部）
追加署名の第3ラウンド候補を方式別に整理した公式ページ。多変数系とMPC-in-the-Head系の分類を確認できる。
【参考記事】
An Efficient Variant of F4 Algorithm for Solving MQ Problem（外部）
本研究の論文。最新版ではType VI・GF(31)でm=21～24を報告し、m=24は従来記録m=20より推定約47,627倍難しいとする。
Fukuoka MQ Challenge：Type VI・m=24 記録詳細（外部）
今回の世界記録の一次資料。n=36・m=24を2025年10月16日付で登録し、実行時間約11日12時間と記す。
Status Report on the Second Round of the Additional Digital Signature Schemes（外部）
NIST追加署名の第2ラウンド公式報告書。2026年5月14日に9候補が第3ラウンドへ進み、多変数系への攻撃にも触れる。
MQ Challenge: Hardness Evaluation of Solving Multivariate Quadratic Problems（外部）
Fukuoka MQ Challengeの設計論文。Type VIがGF(31)上でn≈1.5mの構成をとることを記す一次資料。
M4GB: An Efficient Gröbner-Basis Algorithm（外部）
比較対象M4GBの原論文。Type VI・GF(31)で最大19式までを最長約11日以内で解き、記録を更新したと報告する。
Post-Quantum Cryptography: Additional Digital Signature Schemes（Round 3）（外部）
NIST第3ラウンドの候補を方式別に示す公式ページ。多変数系とMQOMの位置づけを確認できる。
【編集部後記】
mqchallenge.org の Hall of Fame を開くと、Type VI・GF(31) の記録欄に坂田・高木両氏の名前と、m=21からm=24へと伸びていった到達点が並んでいます。最高記録は2025年10月16日付のm=24（n=36）です。何式まで解けたかという数字の推移から、一般的なMQ問題に対する解法能力がどこまで進んだか、その一端が見えてきます。
ただし、実際の多変数署名はUOVのように方式ごとの構造を持つため、この記録だけで各方式の安全な境界線が直接決まるわけではありません。同じくMQ問題に関連する困難性を根拠にするUOVやMAYO、SNOVAは、NIST第3ラウンドで審査の最中です。解読記録がm=24まで届いた今、これらの署名方式が採用時に選ぶパラメータは、どこまでの余裕を見込んで設定されるのか。