OpenAIとAnthropicが数学の難問に突破口　暗号の前提を揺さぶる

OpenAIとAnthropicが、それぞれ社内のAIモデルを使い、計算機科学の長年の仮説「指数時間仮説」を否定する証明を見つけたと発表した。両社が公開した証明は、外部の専門家が検証中だ。

暗号研究者が注目するのは、人間が見積もってきた「計算の難しさ」をAIが覆す可能性だ。暗号は、秘密の鍵を持たない相手には解読に膨大な計算が必要になるように作られている。AIが予想外の解き方を見つけるなら、暗号の解読にかかる時間の見積もりも見直す必要があるのではないか。そんな懸念が出ている。

「これ以上速く解けない」という予想に反証

指数時間仮説が扱うのは、「3-SAT」と呼ばれる論理問題だ。例えば、多数のスイッチについて、「Aはオン、Bはオフ、Cはオンのうち、少なくとも一つを満たす」といったルールをいくつも設ける。すべてのルールを同時に満たすスイッチの組み合わせがあるかを調べる問題だ。総当たりで探すなら、スイッチが一つ増えるたびに、調べる候補は倍になる。

同じ数のスイッチを使う問題でも、条件の組み合わせによって、すぐ答えが分かるものと、計算に時間がかかるものがある。総当たりより速い解き方も見つかっているが、どんな方法を工夫しても、スイッチの数が増えるにつれて計算時間が指数関数的に増えてしまう問題は残る、と考えられてきた。これが指数時間仮説だ。

両社は、そうした時間のかかる問題も含めて、計算時間の増え方を指数関数的な増加よりも緩やかにする方法を見つけたと主張している。正しければ、どんな解き方を工夫しても越えられないと考えられてきた限界を、AIが突破したことになる。

OpenAIは10月26日、自社のAIによる反証を発表した。Anthropicも、自社のClaude研究モデルによる反証を明らかにした。両社は、それぞれの発見日を10月16日としている。

Anthropicによると、Claudeは人間の介入なしに中核となる計算方法を発見した。その後、同社の研究者がClaudeとともに、論文の説明を分かりやすく整えた。

両社は論文に加え、証明の論理をコンピューターで検査できるデータも公開した。外部の専門家による検証も進んでおり、OpenAIの成果については、指数時間仮説の提唱者らが検証を率いている。

暗号を支える「解読には時間がかかる」という前提

Johns Hopkins大学教授のMatthew Green氏は、今回の成果自体が現在の暗号を危険にさらすことはないと、米テクノロジーメディアThe Informationに説明した。とは言うものの、AIが今後、暗号の解読にも予想外の近道を見つける可能性があることを示唆するような成果になっている。解読には膨大な時間がかかるということが前提となって暗号が成立してきたのだが、その前提が崩れるかもしれないわけだ。つまり暗号そのものが成立しなくなる可能性がある。

同氏は「何が難しいかという私たちの直感は、あくまで人間のものだ。人間が難しいと思うかどうかは、もはや重要ではない」と語った。「これなら簡単には解けないだろう」という人間が判断することは、もはや意味がないということになる。

例えばThe Informationが例に挙げるのが、インターネットで広く使われている楕円曲線暗号だ。この暗号では、公開されている情報から、解読に必要な秘密の鍵を割り出すには膨大な計算が必要だと考えられている。このため、秘密の鍵を知らない相手は、簡単には通信内容を読めない。もしAIが鍵を短時間で割り出す方法を見つければ、この暗号を使うサービスは、通信を守る方法を急いで見直す必要がある。

OpenAIの成果を検証しているマサチューセッツ工科大学教授のRyan Williams氏も、今回の成果を「暗号への影響を考えさせられるような発見だ」とThe Informationに語っている。

安全性の見直しは、企業のコストにもつながる

マサチューセッツ工科大学教授のYael Kalai氏は、今回の成果を受けて、米国立標準技術研究所（NIST）が企業などに勧める暗号の安全性の水準を引き上げる可能性があると、The Informationに語った。企業が新たな水準に合わせるには、使っている暗号の安全性を確かめ、足りなければ強化する必要がある。

同氏によると、より解読されにくい暗号を使うには、情報を暗号化したり元に戻したりする処理に、今より多くの計算とメモリーが必要になる。企業が新しい推奨水準に合わせて暗号を強化すれば、通信や取引の安全を守るための費用も増えることになる。

AIの進化でソフトウエアの脆弱性が多数発見されるという事件が続いているが、AIの進化は暗号技術にも大きな課題を突きつけようとしているわけだ。