OpenAI、暗号理論で画期的成果と主張 ビットコインへの即時脅威なし

OpenAIは、自社のAIシステムが指数時間仮説（ETH）を反証したと主張した。ETHは、特定の論理問題の計算困難性に関する長年の前提だ。10月26日の発表を受け、研究者らは独立検証の準備を進めている。開示された結果は、ビットコインへの現実的な攻撃を示すものではない。ここでのETHは暗号資産イーサ（Ether）ではなく指数時間仮説を指す。 同仮説は3SATに関係する。3SATは、一連の論理条件を満たす真偽値の割り当てをコンピュータに求める問題だ。仮説は、最悪ケースの解には変数数に応じて指数関数的に増える時間が必要だとしている。10月17日付、10月25日改訂の原稿は、固定幅ブール式の充足割り当てを正確に数える決定論的アルゴリズムを主張する。準指数時間で実行し、多項式空間を要するとする。準指数時間は問題規模の拡大に伴い指数関数的な上界より緩やかに増えるが、現在のコンピュータで容易に解けることを意味しない。示された上界は多項式時間アルゴリズムを確立せず、P=NP問題も解決していない。P=NP問題は、解を多項式時間で検証できるすべての決定問題が、多項式時間で計算できる解も持つかどうかを問う。 OpenAIは、証明支援系Leanが結果を検証したとしている。ただしLeanの対象範囲注記は、原稿の最も強い主張より弱い準指数時間の上界を示す。独立検証を組織する研究者らは認定を明示的に留保している。主催者の書簡は「われわれの関与は、この主張を認定するものと受け取るべきではない」としている。CryptoSlateは証明全体ではなく、冒頭の1～8ページのみを確認した。 ビットコインの採掘と送金権限は異なるセキュリティ課題だ。採掘者は目標値を下回るブロックヘッダーハッシュを探す。署名は送金権限を示す。BIP340に記述される通り、ビットコインはsecp256k1楕円曲線上のECDSAとSchnorr署名を用いる。BIP340のセキュリティ前提は楕円曲線離散対数とハッシュ関数に関わる。鍵復元は、攻撃者が公開鍵から秘密鍵を取得できるかを問う。SATの最悪ケースに関する仮定を反証しても、それ自体で特定のセキュリティ機構を破る方法が示されるわけではない。現実的な攻撃には、適切な符号化、動作する実装、対象課題のコスト比較が必要だ。SAT式の変数数を、暗号鍵やハッシュのビット長に置き換えることはできない。Leanの対象範囲は、符号化された式の変数と入力長で上界を表す。暗号のビット数を上界に当てはめると、実際の問題を必要な形で表現する工程を飛ばすことになる。 ビットコインは2,016ブロックごとに採掘目標値を調整する。調整は署名権限ではなくブロック生成を左右する。調整によって、独自の採掘上の優位性の重要性がなくなるわけではない。10月7日、ジャスティン・ドレイク氏は、以前のOpenAIの数学に関する発表を受け、「バンカーモード」への備えを促した。ドレイク氏の警告は将来の攻撃可能性に関するもので、以前の発表はECDSAやRSAを実際に破った例を示していなかった。OpenAIの10月26日の主張は別の結果に関するものだ。 ライアン・ウィリアムズ氏は、自身とラッセル・インパリアッツォ氏、モーハン・パトゥリ氏が、秘密保持契約や報酬を伴わない公開・独立検証の手配を依頼されたと述べた。同氏は別に、既存の暗号システムが侵害されているかOpenAIに確認するよう依頼し、暗号システムはどうやら安全なままであると伝えたと述べた。同氏の説明は、OpenAIに依頼した確認に関する伝聞情報であり、独立した暗号監査ではない。OpenAIは実用上の改善にはかなりの追加研究が必要としている。ウィリアムズ氏は開発者が恩恵を受けるかは分からないとし、12カ月以内に進展する可能性も、そうした開発が実現しない可能性も残した。主催者は検証中に結果を公表する予定だ。