11日12時間12分、4基のAMDサーバープロセッサは、方程式でできた迷路を進み続けた。中央に盗まれたパスワードはなく、開けるべき銀行口座もない。目標は、0から30までの整数しか存在しない時計のような世界から36個の数を選び、24本の二次方程式をすべて同時に満たすことであった。

計算が終わったのは2025年10月16日。その意味が公になるまでには、もう少し時間がかかった。査読を経て、東京大学大学院情報理工学系研究科の坂田康亮特任研究員と高木剛教授は、2026年7月17日付で『IACR Transactions on Cryptographic Hardware and Embedded Systems』に手法をオンライン公開した。大学は5日後に発表し、成果は国際会議CHES 2026でも報告される予定だ。

解かれたのは、2015年に始まった公開ベンチマーク「Fukuoka MQ Challenge」の一問である。MQはMultivariate Quadratic、多変数二次方程式の略だ。記録問題は有限体GF(31)上の36変数・24方程式からなり、同じ部門の従来記録、33変数・22方程式の問題より約4万7000倍難しいと研究者は見積もる。

この表現には厳密さが必要だ。新アルゴリズムが実測で4万7000倍高速だった、という意味ではない。4万7000という数字は問題複雑度の推定比較である。またRSA、ウェブ通信、NISTの耐量子標準、実ユーザーの秘密鍵を破ったわけでもない。チームは、電子署名型に生成された一つのベンチマークを解いた。重要なのは攻撃手法である。MQ問題を解く現実のコストが下がれば、暗号設計者が安全なパラメータを選ぶ基準も変わる。

暗号解読は、鍵を壊すだけの営みではない。最良の暗号解読は、社会が価値あるものを預ける前に、その鍵の強さを測る。
36変数世界記録となったType VI問題の未知数。
24方程式同時に成立させなければならない二次制約。
GF(31)計算が31を法として循環する有限体。
99万4320秒記録された実行時間。11日12時間12分。
2011個15変数を推測した後に試した小規模系。
約4万7000倍問題難易度の推定値。実測速度向上ではない。

MQとは、どのようなパズルか

2x＋3y＝7のような一次方程式系なら、行列へ並べ、Gaussの消去法で体系的に解ける。そこへxyのような積、x²のような平方、そして数十の変数同士の相互作用を加えると、景色は変わる。一般的なMQ問題では、複数の二次多項式をすべてゼロにするベクトル（x1, …, xn）を求める。

GF(31)上の小さなMQ問題
  • x² + 3xy + 7y + 5 = 0
  • 4xy + y² + 2x + 9 = 0
  • 加減乗除は31を法として循環する。30＋2は1になる。

有限体では、数値近似で逃げることができない。候補は各方程式を厳密に満たすか、満たさないかのどちらかだ。二次項は可能な相互作用の数を増やし、代数的な消去で方程式を組み合わせると、途中にはさらに高い次数の項が現れる。元の問題はメモリーに収まっても、それを解くための中間構造が膨張し、最終解ではなくメモリーが敵になる。

MQ問題が公開鍵暗号に使えるのは、「落とし戸」を組み込めるからだ。署名者は、秘密裏には簡単に逆算できる特殊構造の方程式系を持ち、それを変換で隠す。公開鍵は難しそうな二次方程式の集まりに見える。検証は速い。署名を代入し、方程式が成り立つか確認すればよい。一方、秘密構造を知らずに偽造するには、難しい公開方程式を解かなければならない。

Fukuoka MQ Challengeは秘密性の主張を取り払い、より純粋な科学的質問を投げる。現在のアルゴリズムとハードウェアで、一般的な方程式系をどこまで解けるか。Type VIは、方程式1本に対し変数がおよそ1.5個ある、電子署名に近い不足決定系をGF(31)上に作る。係数は円周率πの桁から再現可能な形で生成され、主催者が問題と殿堂を公開する。実用暗号そのものではなく、暗号強度を測る走路である。

非線形代数が巨大行列になるまで

中心的な道具はGröbner基底だ。同じ解をもつ多項式系を、代数的な帰結が読みやすく、解を取り出しやすい形へ組み替える。一階段行列の非線形版と説明されることが多い。直感としては有効だが、計算コストは大きく違う。一次方程式の消去では次数は上がらない。多項式の消去では新しい組合せが生まれ、可能な単項式が爆発的に増える。

現代へ続く系譜は、David Hilbertが1890年に行った多項式イデアルの研究まで遡る。1965年、オーストリアの数学者Bruno Buchbergerは基底理論と初の一般アルゴリズムを構築し、指導教員Wolfgang Gröbnerの名を付けた。Buchberger法はS多項式という特殊な組合せを繰り返し作って簡約し、新たな代数的帰結を露出させ、基底を完成させる。

1999年、フランスの計算機代数研究者Jean-Charles FaugèreはF4を発表した。一つずつ多項式を簡約する代わりに、関連する多数の簡約をMacaulay行列へまとめ、疎な線形代数で処理する。最悪計算量を改善したわけではないが、実際には大幅に高速化できる。暗号解読者にとってF4は、抽象的な多項式消去を、どの行を作り、どう保存し、無駄をいつ捨てるかという具体的な競争へ変えた。

行列の各行は多項式を、列はx1x7やx3²x9のような単項式を表す。次数が上がるたび、列は増殖する。候補の多くはゼロへ簡約されるか、新情報を加えない。それでも通常の実装は、行列を作った後で初めて無駄と分かり、時間とメモリーを使ってしまう。

行列を作る前にHilbertに数えさせる

坂田氏と高木氏の中心的発想は、Hilbert級数を予報として使うことだ。Hilbert級数は、方程式系の次数付き代数構造を一変数の級数へ圧縮する。大づかみに言えば、各次数で独立な単項式の「方向」がいくつ残るかを数える。その見通しを先に得れば、計算前半で必要になりそうな組合せだけを選び、巨大な候補群を実体化してから冗長な行を捨てる必要がなくなる。

研究者は前半の戦略をHilbert-driven F4、HDF4と呼ぶ。代数的な挙動が単純でなくなる後半では、Macaulay行列を拡大しにくい臨界対を優先する。世界記録の提出情報にはHDF4とMutant F4（MF4）の併用が記されている。革新は一つの魔法の近道ではない。有用な代数だけをF4へ与え、最悪の行列膨張を起こす餌を減らす、規律ある計算順序である。

さらに実務的な層があった。チームは36変数のうち15個の値を先に推測し、残る小さな方程式系を解いた。4基のAMD EPYC 7763プロセッサ上で、1インスタンス16スレッドを使い、2011個の系を実行した。平均の実時間は約7830秒だった。このハイブリッド法は、大きな外側探索と引き換えに、内側の代数計算をずっと安くする。解と両立する推測へ到達できるかが成功を左右する。

詳細を見ると、奇妙に見える結果も説明できる。同じ2025年10月16日、チームは一回り小さい34変数・23方程式のType VI問題も解いている。だがこちらは約21日半かかり、36変数・24方程式の記録より長い。実時間は単純な階段ではない。推測、並列実行の割り当て、各部分問題の代数的性質、成功枝が現れる順番に左右される。「難しい」はモデル上の複雑度比較であり、観測される時計時間が必ず長くなるという意味ではない。

Type VI記録方程式系手法・ハードウェア報告時間
2023年11月14日33変数 / 22方程式 / GF(31)Hilbert-driven F4、AMD EPYC 7763、12変数を推測18万3307秒、約2日2時間55分
2025年10月16日34変数 / 23方程式 / GF(31)HDF4 + MF4、EPYC 7763×4、13変数を推測185万7440秒、約21日12時間
2025年10月16日36変数 / 24方程式 / GF(31)HDF4 + MF4、EPYC 7763×4、15変数を推測99万4320秒、約11日12時間

福岡から生まれた公開挑戦

高木教授とこのベンチマークとの関係は、今回の記録より古い。2015年4月、Takanori Yasuda、Xavier Dahan、Yun-Ju Huang、高木剛、櫻井幸一の各氏は、Washington, D.C.で開かれたNISTワークショップでMQ Challengeを発表した。目的は、ソルバーを共通かつ再現可能に比較することだった。論文ごとに漸近的な計算量を示したり、異なる計算機や方程式族で結果を報告したりするだけでは比べにくい。共通問題なら、アルゴリズムは同じ地面で競う。

問題群は暗号化型と電子署名型を分け、GF(2)、GF(2⁸)、GF(31)の三つの体を試す。Type I〜IIIは変数の2倍の方程式をもち、過剰決定の暗号化状況を表す。Type IV〜VIは方程式の約1.5倍の変数をもち、多変数署名に多い不足決定系を表す。東京大学の記録は、その最後のGF(31)部門、Type VIである。

記録は単にプロセッサが速くなっただけでなく、XL、F4、Gröbner基底計算の改良によって伸びた。M4GBは2017年にType VIの前線を20方程式へ進めた。坂田氏と高木氏は2023年、Hilbert駆動法で21、22方程式へ到達。新研究は23、24へ進んだ。方程式が2本増えただけに見えるかもしれない。しかし暗号の難しさは組合せ的に増えるよう設計される。この地形では、次の一歩は山全体を広くする。

公開鍵から量子時代の期限へ

現代の公開鍵暗号は、発想の断絶から始まった。1976年、Whitfield DiffieとMartin Hellmanは、盗聴され得る公開通信路を通じて二者が共有秘密を作る方法を示した。1978年、Ronald Rivest、Adi Shamir、Leonard Adlemanは、大きな合成数の素因数分解の難しさに依存するRSAを発表した。離散対数に基づく関連方式も、ウェブ通信、ソフトウェア更新、本人確認、電子署名を守るようになった。

1994年、Peter Shorは、十分に能力のある量子計算機なら、素因数分解と離散対数を入力サイズの多項式時間で解けることを示した。現代インターネットの鍵長を攻撃できる誤り耐性量子計算機はまだない。しかし長期間秘密にすべき情報は今収集され、後で復号される恐れがある。暗号基盤の変更には10年かかることもある。だから政府と標準化機関は、機械が完成する前に移行している。

多変数暗号は別の数学的道を進んだ。1988年、松本勉氏と今井秀樹氏は、署名・暗号化に使う公開二次多項式組を提案した。Jacques Patarinは1995年、変換の下に隠れた関係を露出させて方式を破り、その後Hidden Field EquationsやOil and Vinegarなど新しい系統を開発した。1999年のUnbalanced Oil and Vinegarは、均衡型が攻撃された後、変数構造を変えた方式である。

歴史は循環する。設計者は署名を容易にする構造を隠し、暗号解読者は構造が多すぎる場所を使って偽造を容易にする。Oil and Vinegarの多層型であるRainbowは、NIST最初の耐量子競争で最終候補まで進んだが、改良された構造攻撃の波を生き残れなかった。それはMQ暗号がすべて無意味だと証明したのではない。無作為方程式を解く一般的難しさは、方式安全性の一層にすぎないと証明した。落とし戸、鍵圧縮、実装は、いずれもランダム問題にはない近道を生み得る。

2026年、多変数署名はどこにいるか

NISTが2024年8月に公開した最初の耐量子標準に、多変数方式は入らなかった。ML-KEMとML-DSAは構造化格子、SLH-DSAはハッシュ関数に基づく。別の格子署名FalconはFIPS 206として準備中で、符号ベースのHQCは2025年に追加暗号化方式として選定された。

それでも多変数の枝は生きている。2026年5月、NISTは追加電子署名候補9方式を第三ラウンドへ進めた。MAYO、QR-UOV、SNOVA、UOVの四つは多変数系で、MQOMも別の証明システム設計を通じてMQ問題を利用する。魅力は高速検証と非常に小さな署名だ。長年の代償は大きな公開鍵であり、余分な代数構造で鍵を圧縮しようとすると、新たな攻撃面を生むことがある。

この環境で東京大学の記録は意味をもつ。NISTは完成した方式を評価し、Fukuoka MQ Challengeは一般方程式解法を評価する。両者を同一視することはできないが、互いに情報を与える。一般攻撃はすべてのMQ方式の下に床を置く。方式固有攻撃は天井から落とし戸を探す。安全なパラメータには、その間の余裕が必要だ。

世界記録が語ること、語らないこと

結果が支持すること支持しないこと
新しいF4変種は、行列成長を抑え、大きなType VI問題を解けた。「東京大学が耐量子暗号を破った」。
36変数・24方程式の問題は、従来記録より約4万7000倍難しいと推定される。アルゴリズムの実測速度が4万7000倍になった。
一般MQ攻撃のコストを新手法で再評価する必要がある。すべてのMQ署名、すべてのパラメータが危険になった。
Hilbert級数により、行列構築前に冗長な代数を省ける。MQやGröbner基底計算の最悪計算量が消えた。
公開ベンチマークが再現可能な暗号解析を前進させた。実ユーザーの鍵、暗号文、NIST標準が侵害された。

ベンチマークと破壊の区別は、言葉を弱めるための注意ではない。安全工学の本体である。36変数問題は実用保護に選ぶパラメータより小さいが、そのコストは、小さな問題からの外挿が楽観的すぎたかを示す。一方、ランダム問題を一つ解けたことより、特定方式の隠れた対称性を使う攻撃の方が、その方式について多くを語る場合がある。

ハードウェアも重要だ。AMD EPYC 7763を4基という構成は大きいが、量子計算機でも国家級スーパーコンピューターでもなく、通常のサーバー技術である。ただし提出記録は、あらゆる実装を横断して正規化した普遍コストではない。メモリー使用量、コンパイラ、有限体演算、スレッド割り当て、推測インスタンスの分布が性能を変える。追試と独立比較によって、改善がどこまで広く移植できるかが分かる。

残された問い

東京大学チームは、二つの直近課題を挙げる。新しいCPU命令の活用と、より広い並列環境への展開だ。どちらも現在の実証を、より速く拡張可能なソルバーへ変え得る。さらに大きな科学的問いは、方程式規模、有限体、方程式と変数の比率が変わってもHilbert駆動選択が優位を保つかである。Type VI向けに強い方法が、過剰決定の暗号化型問題や、実署名の高度に構造化された公開鍵で同じように働くとは限らない。

量子計算は別の層を加えるが、魔法の杖ではない。Shorのアルゴリズムが素因数分解と離散対数へ壊滅的なのは、量子計算で利用できる構造があるからだ。一般MQを同じように効率よく解く量子アルゴリズムは知られていない。Grover型探索は全数探索の指数を一部減らし、将来のハイブリッド法が代数攻撃を改善するかもしれない。しかし「耐量子」は、量子・古典のあらゆる進歩に永久不変という意味ではない。現在知られる最良攻撃に対してパラメータを選ぶ、という意味である。

実装安全性も記録の範囲外だ。数学的に健全な署名でも、処理時間、消費電力、故障注入、乱数不良から秘密が漏れ得る。多変数方式の大きな鍵は、帯域と保存の費用を生む。標準化は、安全性証明、暗号解析、性能、実装可能性、方式多様性を総合しなければならない。「最も難しそうな方程式」だけを王にすることはできない。

攻撃者が定規を作る

暗号は、独特な公開敵対関係によって進歩する。設計者は方式を公開し、専門家へ解体を求める。挑戦問題の主催者は方程式を公開し、解読者へ到達点を競わせる。成功した攻撃は数年の設計を消し去ることがあるが、弱い方式が社会基盤になるのも防ぐ。記録解法が方程式を2本しか増やさなくても、推定値を証拠へ置き換える。

坂田氏と高木氏の成果は、二つの長い歴史を結ぶ。一つはDiffie–Hellmanの公開路鍵共有から、現在進む量子時代への移行まで続く秘密保護の歴史。もう一つはHilbertの数え上げからBuchbergerの基底、Faugèreの行列、現代の多コアサーバーへ続く記号代数の歴史だ。多項式空間の形を理解する数学が、計算機へ「何を計算しないか」を教えることで新手法は機能する。

99万4320秒が示した最も重要な教訓は、そこにあるのかもしれない。総当たりだけが勝ったのではない。数学がプロセッサの注意を絞ったから、計算は終わった。得られた36個の有限体要素そのものより、それへ至る道の方が価値をもつ。他の研究者が検証し、改善し、より安全な余裕を設定するために使える道である。

東京で実用の鍵が開いたわけではない。もっと手前にある、未来の安全にとって有用な仕事が完了した。実行可能性の端が、もう一度測られた。その端は以前より遠くへ進み、そこより先へ防御を設計するすべての暗号研究者は、より鋭い定規を手にした。

主要資料・参考文献

本稿は、2026年の査読論文・大学発表と、2025年10月16日に記録されたベンチマーク解法の時系列を区別した。「約4万7000倍」は研究者による問題難易度の相対推定であり、実測上のアルゴリズム加速とは扱っていない。