OpenAIのETH反証主張、研究者が独立検証へ

OpenAIは、特定の難しい問題を解くのに必要な時間についての予想である指数時間仮説（ETH）を反証したと主張しています。研究者らは独立検証を計画していますが、この結果はビットコインへの実用的攻撃を示すものではありません。CryptoSlateの検討範囲は論文の冒頭1～8ページに限られ、証明全体を評価していません。検証を主催する研究者らは、参加を主張の認証と受け取らないよう述べました。

10月17日付で10月25日に改訂された論文は、幅が固定されたブール式の充足割り当て数を厳密に数える決定的アルゴリズムについて、劣指数時間かつ多項式空間で動作すると主張しています。記事によると、これは問題の規模が大きくなるにつれて実行時間が指数上界より遅く増えるという意味であり、現在のコンピューターで問題が簡単になるという意味ではありません。公表された上界は多項式時間アルゴリズムを示すものではなく、解の検証が多項式時間でできるすべての問題を多項式時間で解けるかというP=NP問題にも決着をつけません。OpenAIは結果を証明支援系Leanで検証したとしていますが、形式化の範囲に関する注記では、論文の最も強い主張より弱い時間上界が示されています。

ビットコインの採掘と送金承認は、別々のセキュリティ課題です。採掘では目標値を下回るブロックヘッダーのハッシュを探し、署名は送金を承認します。ビットコインは楕円曲線secp256k1上のECDSA署名とSchnorr署名を使いますが、公開鍵から秘密鍵を復元することは、最悪ケースのSAT問題を解くこととは別の課題です。記事は、ETHの主張がこれらの仕組みを破る方法を示していないと指摘しています。実用的な攻撃には適切な符号化、実装、コスト比較が必要です。SAT式の変数数を暗号鍵やハッシュのビット長にそのまま置き換えることもできません。ビットコインは採掘目標値を2,016ブロックごとに調整しますが、これはブロック生成に関する仕組みで、署名による承認とは別です。

このETHの主張は、10月7日にJustin Drakeが、OpenAIによる以前の数学分野の発表を受けて「バンカーモード」の備えを呼びかけた、CryptoSlate掲載の議論とは別件です。Ryan Williamsによると、同氏とRussell Impagliazzo、Mohan Paturiは、秘密保持契約（NDA）も報酬もない公開検証の取りまとめを依頼されました。Williamsは別途、既存の暗号システムが破られていないかOpenAIに確認を求め、問題はなさそうだとの返答を伝えたと述べています。これは伝聞であり、独立した暗号監査ではありません。OpenAIは実用的な改善には大幅な追加研究が必要だとしています。Williamsは開発者が恩恵を受けるかは分からないとし、12か月以内に進展する可能性も、何も起きない可能性もあると述べました。主催者は検証の進行に合わせて調査結果を共有する予定です。

OpenAIは、特定の難しい問題を解くのに必要な時間についての予想である指数時間仮説（ETH）を反証したと主張しています。研究者らは独立検証を計画していますが、この結果はビットコインへの実用的攻撃を示すものではありません。CryptoSlateの検討範囲は論文の冒頭1～8ページに限られ、証明全体を評価していません。検証を主催する研究者らは、参加を主張の認証と受け取らないよう述べました。

10月17日付で10月25日に改訂された論文は、幅が固定されたブール式の充足割り当て数を厳密に数える決定的アルゴリズムについて、劣指数時間かつ多項式空間で動作すると主張しています。記事によると、これは問題の規模が大きくなるにつれて実行時間が指数上界より遅く増えるという意味であり、現在のコンピューターで問題が簡単になるという意味ではありません。公表された上界は多項式時間アルゴリズムを示すものではなく、解の検証が多項式時間でできるすべての問題を多項式時間で解けるかというP=NP問題にも決着をつけません。OpenAIは結果を証明支援系Leanで検証したとしていますが、形式化の範囲に関する注記では、論文の最も強い主張より弱い時間上界が示されています。

ビットコインの採掘と送金承認は、別々のセキュリティ課題です。採掘では目標値を下回るブロックヘッダーのハッシュを探し、署名は送金を承認します。ビットコインは楕円曲線secp256k1上のECDSA署名とSchnorr署名を使いますが、公開鍵から秘密鍵を復元することは、最悪ケースのSAT問題を解くこととは別の課題です。記事は、ETHの主張がこれらの仕組みを破る方法を示していないと指摘しています。実用的な攻撃には適切な符号化、実装、コスト比較が必要です。SAT式の変数数を暗号鍵やハッシュのビット長にそのまま置き換えることもできません。ビットコインは採掘目標値を2,016ブロックごとに調整しますが、これはブロック生成に関する仕組みで、署名による承認とは別です。

このETHの主張は、10月7日にJustin Drakeが、OpenAIによる以前の数学分野の発表を受けて「バンカーモード」の備えを呼びかけた、CryptoSlate掲載の議論とは別件です。Ryan Williamsによると、同氏とRussell Impagliazzo、Mohan Paturiは、秘密保持契約（NDA）も報酬もない公開検証の取りまとめを依頼されました。Williamsは別途、既存の暗号システムが破られていないかOpenAIに確認を求め、問題はなさそうだとの返答を伝えたと述べています。これは伝聞であり、独立した暗号監査ではありません。OpenAIは実用的な改善には大幅な追加研究が必要だとしています。Williamsは開発者が恩恵を受けるかは分からないとし、12か月以内に進展する可能性も、何も起きない可能性もあると述べました。主催者は検証の進行に合わせて調査結果を共有する予定です。