OpenAI Claims Cryptography Breakthrough, No Immediate Threat to Bitcoin

OpenAI claims its AI system has disproved the Exponential Time Hypothesis, a longstanding assumption about the computational difficulty of certain logic problems. The October 26 announcement has prompted researchers to organize an independent examination. The disclosed result does not demonstrate a practical attack on Bitcoin.

The abbreviation ETH refers here to the Exponential Time Hypothesis, not Ether. The hypothesis concerns 3-SAT, which asks computers to assign true-or-false values that satisfy a set of logical conditions. The hypothesis holds that worst-case solutions require time that grows exponentially with the number of variables.

The manuscript, dated October 17 and revised October 25, claims a deterministic algorithm for exactly counting satisfying assignments of fixed-width Boolean formulas. The manuscript claims subexponential running time and polynomial space requirements. Subexponential running time grows more slowly than an exponential bound as problem size increases, but that does not mean current computers can solve the problem easily. The disclosed bound neither establishes a polynomial-time algorithm nor resolves P=NP. The P=NP question asks whether every decision problem with solutions verifiable in polynomial time also has solutions computable in polynomial time.

OpenAI says the proof assistant Lean verified the result. However, the Lean scope note describes a weaker subexponential time bound than the manuscript's strongest claim. The researchers organizing the independent examination have explicitly withheld certification. The organizers' letter states, "Our involvement should not be taken as certification of the claim." CryptoSlate examined only introductory pages 1-8, rather than the complete proof.

Bitcoin mining and authorization to spend involve different security tasks. Miners seek a block-header hash that falls below a target. Signatures demonstrate permission to spend. Bitcoin uses ECDSA and Schnorr signatures over the secp256k1 elliptic curve, as BIP340 describes. The security assumptions described in BIP340 involve elliptic-curve discrete logarithms and hash functions. Key recovery asks whether an attacker can obtain a private key from the corresponding public key.

Disproving a worst-case SAT assumption does not itself demonstrate a way to defeat those specific security mechanisms. A practical attack would require an appropriate encoding, a working implementation and a comparison of costs for the targeted task. A SAT formula's variable count cannot be substituted for a cryptographic key's or hash's bit length. The Lean scope expresses the bound in terms of the encoded formula's variables and input length. Inserting a cryptographic bit count into the bound would bypass the necessary representation of the actual problem.

Bitcoin adjusts the mining target after every 2,016 blocks. The adjustment governs block production rather than signature authorization. The adjustment would not eliminate the importance of a private mining advantage. On October 7, Justin Drake urged preparations for "bunker mode" following an earlier OpenAI mathematics announcement. Drake's warning concerned a potential future attack, while that earlier announcement had demonstrated no practical break of ECDSA or RSA. OpenAI's October 26 claim concerns a separate result.

Ryan Williams said Williams, Russell Impagliazzo and Mohan Paturi had been asked to arrange an open, independent examination without nondisclosure agreements or payment. Williams separately said Williams had asked OpenAI to check whether existing cryptosystems were compromised and relayed that the cryptosystems apparently remained safe. Williams's account is second-hand information about a check requested from OpenAI, not an independent cryptographic audit.

OpenAI says substantial additional research is necessary for practical improvements. Williams said Williams did not know whether developers would see benefits, leaving open both progress within 12 months and no such development. The organizers plan to publish findings during the examination.