Lance Fortnowは20年以上にわたって計算複雑性のブログを書き続けている人物で、軽々しく騒ぎ立てるタイプではありません。そんな彼が今回の主張について書いた記事は、慎重な一文で締めくくられていました。「自分で証明を検証したわけではないが、指数時間仮説はもはや破綻したと考えて差し支えない」(Computational Complexity)。
この主張を出したのは2つのラボです。ChatGPTを手がけるOpenAIは、自社のモデルが指数時間仮説(Exponential Time Hypothesis、通称ETH)を反証したと発表しました。その数時間後には、Claudeを開発するAnthropicも独自の反証を公開しています(両アシスタントの比較はこちら)。その後、このニュースは数学者同士の争いや、世界の暗号への不安と結びつけて報じられました。私たちは両ラボの公式資料、専門家のコメント、報道を読み込みました。結論ははっきりしています。この結果はおそらく本物で、理論研究者にとっては重要ですが、データの守り方を変える理由にはなりません。3つの見出しのうち2つは別の論争の話で、残る1つは動向についての話です。
指数時間仮説とは、かんたんに言うと何?
まず3-SATというパズルから始めましょう。n個のオン・オフのスイッチがあり、「AまたはBでないまたはC」という形の条件が長々と並びます。すべての条件を満たすスイッチの設定を見つけるのが課題です。ある設定が正しいかどうかの確認は簡単です。難しいのは、設定を見つける方です。数独で、完成した盤面の検証は簡単でも、空白の盤面を埋めるのは大変なのと同じです。
ETHは1999年にRussell ImpagliazzoとRamamohan Paturi(Francis Zaneとの共同研究)が提唱したもので、3-SATを解くアルゴリズムはどれも、ある固定の正の定数cに対して2^(c×n)のように増える時間を必要とする、という主張です(Fortnow)。ダイヤルが1つ増えるごとに作業量が一定の倍率(たとえば1.3倍)で増えていく、ダイヤル式の錠前を思い浮かべてください。ETHは、その倍率を小さくすることはできても、1にすることはできないと言っています。
今回の反証は、式が大きくなるにつれてこの倍率が1に近づいていくと主張しています。Fortnowによると、OpenAIの論文が示す実行時間は、おおよそ2の「n × log log n ÷ √(log n)」乗です。それでも速いとは言えません。どんな固定の倍率よりも増え方が緩やかになる、というだけです。Anthropicの資料もはっきり述べています。「この結果は純粋に漸近的なものであり、実際に式を解く場面については何も言っていない」(Anthropic)。
なぜ理論研究者たちはこれほど注目したのでしょうか。ETHは、何百もの論文で「この問題はこれ以上大幅には速く解けない」ことの根拠として使われてきたからです(OpenAI)。仮説が偽なら、そうした困難性の議論は見直しが必要になります。ただしFortnowは、「ETHやSETHが成り立たないからといって、そこから導かれた結論が誤りだということにはならない」と指摘しています。
通常より検証は進んでいるが、決着にはほど遠い
ここまでの検証は、たいていの大きなブレークスルーが最初の1週間で受けるものより手厚いです。OpenAIによると、同社のモデルは発表の10日前に反証を見つけ、その証明はLeanで形式化されました。Leanは、検証できるステップしか受け付けない証明チェッカーです(OpenAI)。Anthropicは、社内のClaudeモデルが自社版を見つけ、Leanのファイルも AIモデルが書いたと述べています(Anthropic)。
その後、人間の研究者も加わりました。カーネギーメロン大学のRyan O'Donnellは証明を書き直した解説を公開し、Fortnowによれば Shiva Kintaliも別の解説を公開しています。どちらも最良の評価式よりも簡潔さを優先したものです。Timothy Gowersは「これが偽だというのは非常に意外で、重大なことだ」と述べました(Business Insider)。
正式に検証を任されているのは、Impagliazzo、Paturi、そしてMITのRyan Williamsです。WilliamsはTechCrunchに対し、証明の一部は定型的だが「二つ三つ、異質に見える部分がある」と語っています。Business Insiderによれば、Williamsはこの結果にお墨付きを与えておらず、グループは関与が承認を意味するものではないとしています。Anthropic自身のリポジトリからもう一点注意があります。Leanは証明を検証しますが、「このファイルが論文の内容と同じことを述べているかを確かめる機械はない」ため、人間が短い記述ファイルを読む必要があります。そのために、このファイルは短くしてあるとのことです。
私たちの見方はこうです。2つのラボからの主張で、機械検証済みの証明と人間による書き直しが数日のうちにそろうのは、異例なほど強力です。それでも、専門家グループと学術誌が認めるまでは、あくまで主張にとどまります。
数学者たちの争いは、この結果をめぐるものなのか?
ほとんど違います。BBCが報じた「数学者同士の衝突」は、別の問題についてのものです。この記事が扱っているのはナビエ–ストークス方程式をめぐる論争です。NYUのTristan Buckmasterが、OpenAIのCodexツールに保存していた自分の草稿が、OpenAI自身の研究に使われた可能性はないかと問題提起しました。OpenAIは、社内の誰も相手チームの研究を見ておらず、彼のプロンプトが「システムに何らかの影響を与えることはあり得なかった」と述べています。
Scientific Americanの「出し抜かれた」という見出しは、物理学の問題であるヤン–ミルズ理論についてのものです。同誌は、OpenAIがEthan Sussmanに先んじたようだと伝えています。SussmanはAnthropicのLevent Alpögeと共同で証明に取り組んでいました。AlpögeはXで異議を唱えました。これらはいずれも、3-SATのアルゴリズムが機能するかどうかとは関係がありません。
ETHをめぐる対立は、進め方についてのものです。Williamsは以前のOpenAIの発表を「数学者に対するDDoS攻撃」と呼びました(X)。それでも今回は協力に応じています。Scientific Americanによると、3つの結果のうち2つについてのOpenAIのやり方は、AIと数学に関する自社の専門家諮問グループが出した明確化の声明に反していました。また、その背景にあるプロンプトと思考の連鎖(chain-of-thought)は今も非公開です。ETHについては、OpenAIは証明を公開し、カンファレンスの費用を支援することに同意しています。
RSAやスマホの暗号は破られるの?
いいえ。少なくとも、この経路では破られません。ここまで言い切れるのは、理由が具体的だからです。第一に、このアルゴリズムが解くのはk-SATです。Fortnowは、「Subset SumやTraveling Salesmanについては何ももたらさない」と強調しています。それらを3-SATに変換すると変数の数が増えすぎるためです。第二に、RSAの安全性は巨大な数を2つの素数に分解する難しさに基づいています(Financial Timesはその手法を名前を出さずに説明しています)。これは論理式を充足させる問題とは別の問題で、私たちが読んだ資料のどれも、新しいアルゴリズムがそこに及ぶとは述べていません。第三に、この評価は漸近的なものです。現存するどのマシンでも、2,048ビット鍵について何かが変わるわけではありません。
Williamsは、当然の懸念をOpenAIのサイエンス責任者Dan Robertsにぶつけました。TechCrunchによると、Williamsは「今、安全でなくなったものはあるか」と尋ね、OpenAIは確認済みで、解読につながることはないと「ある程度確信している」ようだと伝えました。これは伝聞で、未公開の情報ですので、その分割り引いて受け取ってください。Williamsは、アルゴリズムが改良されれば、一部の鍵サイズは破られたとみなされる可能性があるとも述べています。
根底には、本物の未解決問題があります。Williamsは「コンピュータ科学者はみな、P = NPが成り立つ可能性をもう少し重く見るべきだろう」と言う一方、John D. Cookは「P = NPの真偽はいまだ不明だ」と指摘しています(Business Insider)。Williamsは、今回のアルゴリズムが最良のものだとも考えていません。もっと鋭いアルゴリズムが現れれば、議論は変わります。
Financial Timesの記事が扱うのは、この証明ではなく動向
FTの記事は、AIの数学能力の向上と暗号全般についての内容で、私たちが読めた範囲の本文にはETHへの言及がありません。取材先の発言は抑制的です。オーストラリアの数学者Geordie Williamsonは、インペリアル・カレッジの聴衆に向けて、AIは「難しさという概念の根本的な再構築」を引き起こしており、衝撃が起こると覚悟すべきだと語りました。マンチェスター大学のDaniel Shiuは、AIが暗号を破ることを「より数学的な形式の暗号」にとっての「重大なリスク」と呼び、「成熟度の低い」耐量子アルゴリズムをいくつか挙げました。FT自身は、AIが「中核となる暗号方式をまだ破っていない」と書いています。
Scott Aaronsonは、気になる点を付け加えました。暗号はOpenAIの以前の376本の論文リストに見当たらず、自身の投稿の追記では、AI企業が自社モデルでプロトコルを破れるか調べ始めたと、情報源から聞いたと書いています。具体的な名前は挙げておらず、私たちにも分かりません。
私たちの見立てでは、懸念すべきは新しい方式であり、ブラウザで使われている方式ではありません。NISTの2024年の標準には、格子ベースの方式が2つ含まれています。さらに、別種の数学に基づく3つ目の署名標準があり、最初の方式に脆弱性が見つかった場合の予備として用意されています。
中小企業が実際にすべきこと
ほとんど何もありません。急ぐ必要もありません。以下のツリーで、重要だと考える3つのケースを整理しています。
この件とは関係なく、身につけておく価値のある習慣が1つあります。英国の規制当局はFTに対し、暗号に対するAIや量子のリスクへの備えについて「企業は行動を待つべきではない」と述べ、BTは自社の暗号を「標準、技術、脅威の変化に応じて、より容易に変更できる」ようにしたいと語りました。小さな会社であれば、ソフトウェアを最新に保ち、ベンダーにアルゴリズムをどう入れ替えるのか尋ねる、ということになります。ベンダーに聞くべき質問は、AIツールにデータを預けられるかを見極めるフレームワークで扱っています。また、ToolRankのSecurity & Privacyボードでは、カテゴリ別にツールを確認できます。
「決着した」と言われる前に見ておきたい3点
注目すべき点は3つです。1つ目は、Impagliazzo、Paturi、Williamsによる専門家グループの報告と、OpenAIが資金提供に同意したカンファレンスです。2つ目は、Leanの記述ファイルを第三者が独立して読み込むことです。微妙な誤りが潜むとすれば、そこだからです。3つ目は学術誌での査読ですが、今のところその兆候は見つかっていません。最初の1つが出てくるまでは、「ほぼ確実に反証された」と表現するのが妥当でしょう。