Blog/AI & Innovation
AI & Innovation

OpenAI Exponential Time Hypothesis Claim: Does AI Break Encryption? What Is Verified and What Gulf and Egypt Teams Should Do

i
iFynx StudioOct 26, 2026 · 18 min read
Handwritten mathematical formulas in white chalk on an old dark-red blackboard

Short answer: The OpenAI Exponential Time Hypothesis claim is that an internal OpenAI model has proved ETH, a quarter-century-old conjecture about how hard Boolean satisfiability (3-SAT) is, to be false. OpenAI announced it on 26 October 2026 together with a maths result (local smoothing, and with it Kakeya and Stein restriction) and a physics result (existence of 4D Yang–Mills and QCD, not the Clay mass gap). All three are OpenAI claims now under expert review. The ETH claim is a subexponential algorithm, not P = NP, and it does not break RSA, ECC or AES. Banks and fintechs in the Gulf and Egypt should not make panic changes, but this is a good moment to finish the cryptographic inventory and crypto-agility work they already owe regulators.

Update, 2 November 2026, 22:15 Asia/Gaza

In its own post on the Navier–Stokes Millennium Prize Problem, OpenAI says an internal system of about 10,000 concurrent agents reached a proof after roughly 88 hours that the Navier–Stokes equations can develop a singularity in finite time, with a further 17 hours for Lean formalization and verification. OpenAI says it does not intend to claim the Millennium Prize. The claim, like the others in this article, still needs independent review by mathematicians.

The OpenAI Exponential Time Hypothesis announcement landed late on 26 October 2026. Ryan Williams of MIT posted at 21:35 UTC “An internal model at OpenAI has produced a claimed refutation of ETH!”, and OpenAI’s Dan Roberts shared the company’s announcement a minute later. That was 23:35 in Gaza and 00:35 on 27 October in Riyadh and Cairo. The obvious question, and an easy clickbait headline, is whether AI has just broken encryption. It has not. The ETH here is a complexity-theory conjecture, not the cryptocurrency, and nothing in the release claims to touch deployed cryptography.

This explainer separates what OpenAI claims from what independent experts have confirmed, which so far is nothing beyond the fact that a review is under way. It explains in plain language why ETH matters, why RSA, ECC and AES do not depend on it, and what product and security teams in the UAE, Saudi Arabia and Egypt should actually do this quarter. It also covers how to check AI-produced proofs and code. For OpenAI’s earlier maths claim and the disclosure debate around it, see our September analysis of OpenAI’s maths claim and the IAS advisory group.

Key facts, with dates and sources

  • 16 October 2026: OpenAI says its AI produced a natural-language disproof of ETH. It was formalized in Lean on 17 October (OpenAI).
  • 18–19 October 2026: AI output proving Sogge’s 1991 local smoothing conjecture in every dimension, formalized in Lean the next day. OpenAI says this also resolves the Kakeya and Stein restriction conjectures in all dimensions.
  • 9 and 18 September 2026: AI proofs of Yang–Mills existence and then QCD existence in four dimensions. The Lean formalization of Yang–Mills existence finished on 16 October. These materials are not public yet.
  • 26 October 2026: OpenAI publishes “Working with academic communities to build scientific understanding” and adds the ETH and local-smoothing papers with Lean files to github.com/openai/math (history).
  • Claimed bound: for every fixed k ≥ 2, a deterministic algorithm counts the satisfying assignments of a k-CNF formula with n variables and m clauses in time (n+m)^O(1) · 2^(n/(log n)^(1/2+o(1))), using polynomial space (paper). This is subexponential, not polynomial.
  • Reviewers: Russell Impagliazzo and Ramamohan Paturi (UC San Diego, ETH’s original proposers with Francis Zane) and Ryan Williams (MIT) for ETH; a group led by Nobel laureate David Gross with Michael Douglas, Arthur Jaffe, Igor Klebanov and Nikita Nekrasov for physics. OpenAI says participation is voluntary and unpaid, with no NDAs (OpenAI).
  • Status on 27 October 2026: no expert group has confirmed any of the three results. The Clay Mathematics Institute still lists Yang–Mills and the Mass Gap as unsolved (Clay).

What is the Exponential Time Hypothesis, in plain language?

Take a logic puzzle with n yes/no switches and a list of rules, each involving three switches, such as “switch 4 is on, or switch 9 is off, or switch 17 is on”. Is there any setting of the switches that satisfies every rule? That is 3-SAT, the classic hard problem of computer science. Trying every combination takes 2^n steps. Cleverer algorithms do better, but every known method still needed time that grows like c^n for some constant c greater than 1.

The Exponential Time Hypothesis, proposed by Russell Impagliazzo and Ramamohan Paturi with Francis Zane in papers published in 2001, says this is unavoidable: no algorithm can solve 3-SAT in time 2^(o(n)). OpenAI notes that ETH has been used in “hundreds of papers” to argue that problems in graph theory, computational biology, databases and computational geometry cannot be solved much faster. ETH is a stronger assumption than P ≠ NP. If it is false, P ≠ NP can still be true.

What exactly does OpenAI claim, and what does the paper actually prove?

OpenAI’s blog says: “Surprisingly, our system has recently proved that the ETH is false, a result that was subsequently verified in Lean.” The AI-written manuscript in the repository is titled “The Exponential Time Hypothesis is False” and is dated 25 October 2026. Its abstract describes a deterministic algorithm that exactly counts the satisfying assignments of an arbitrary k-CNF formula, so it does more than decide whether one exists, in time (n+m)^O(1) · 2^(n/(log n)^(1/2+o(1))) and polynomial space. Replying to a follower, Williams also pointed out a consequence for circuit complexity: “Assuming their claim holds, E^(NP) does not have linear size circuits!” (post).

Williams summarised the headline bound in one line on X: “it’s claimed that 3SAT on n variables is in about exp(n/(log n)^{1/2+o(1)}) time” (post). In words, the exponent shrinks by a factor that grows only like the square root of log n. That is enough to break ETH as a mathematical statement. It is nowhere near a polynomial-time algorithm.

One detail shows why reading the fine print matters. OpenAI’s own Lean scope note says the Lean formalization proves a slightly weaker subexponential bound, than the sharpest bound in the manuscript: an exponent of about n(log log n)^2/√(log n) instead of n·log log n/√(log n). Both bounds are still subexponential, so the ETH claim is unaffected. But the machine-checked statement and the paper’s headline are not word-for-word the same, and that is exactly what reviewers check.

Who is verifying it, and what have they said?

OpenAI asked outside experts to act as “shepherds”. For ETH the group is led by Russell Impagliazzo and Ramamohan Paturi of UC San Diego, two of the people who proposed ETH, and Ryan Williams of MIT, who has refuted strong versions of it. In an open letter to the community the three write: “Our involvement should not be taken as certification of the claim. A result of this significance requires careful, independent scrutiny.” They also write: “If the claim is correct, it will change an important part of theoretical computer science.”

Under the principles OpenAI published, participants sign no non-disclosure agreements, are unpaid, and speak for themselves, not for OpenAI. OpenAI says it agreed to the group’s requests to make all raw data public and to fund a conference on the implications (OpenAI). The letter also raises the uncomfortable questions: early access, conflicts of interest, and how to credit people who check, fix and explain AI-generated results. OpenAI says it does not seek academic credit for these discoveries.

The maths and physics claims: local smoothing, Kakeya and Yang–Mills

Local smoothing, Kakeya and Stein restriction

Christopher Sogge’s 1991 local smoothing conjecture is about waves: the most extreme focusing of a wave must be short-lived. OpenAI notes that Guth, Wang and Zhang proved it in two spatial dimensions in 2019, and Wang and Zahl proved the Kakeya conjecture in three dimensions in 2025. OpenAI says its models proved local smoothing in every dimension using “a novel auxiliary partial differential equation”, and that this resolves the Kakeya and Stein restriction conjectures in all dimensions. The repository’s wording is more precise: it gives Stein’s spherical restriction estimates “throughout the interior of the conjectured range”. For this result OpenAI released the AI output and Lean proof directly and left mathematicians to organise their own review.

Yang–Mills and QCD: existence, not the mass gap

The physics claim is a mathematically rigorous existence proof for certain interacting quantum field theories in four dimensions, including quantum chromodynamics (QCD) and a unified completion of the Standard Model (the simplest grand unified theory containing its gauge fields and fermions). OpenAI says it builds on Balaban’s approach in constructive field theory. As a subproblem, the work includes the existence of pure Yang–Mills theory, which OpenAI calls “part of” the Clay Millennium Prize problem. The Clay problem also requires proving a mass gap. OpenAI does not claim that, and the Clay page still lists the problem as unsolved. The Gross group has chosen not to release the AI-produced material yet and will write the work up itself. So for now there is nothing public to check.

Does the OpenAI Exponential Time Hypothesis result break encryption?

This is the question Gulf CISOs will get from their boards this morning. The careful answer is no, not the encryption that protects banking apps, HTTPS, payment cards or blockchains, and no one involved has claimed otherwise. Here is why:

  • RSA rests on the difficulty of factoring large numbers. Factoring is not believed to be NP-complete, and a classical subexponential algorithm for it (the number field sieve) has existed for decades. RSA key sizes such as 2048 bits are chosen with that algorithm in mind. A subexponential SAT algorithm adds nothing that RSA does not already assume exists.
  • ECC (elliptic-curve cryptography, used in TLS, mobile banking, ZATCA stamps and Bitcoin signatures) rests on the elliptic-curve discrete logarithm problem. Its security comes from the absence of good attacks on that specific algebraic problem, not from ETH.
  • AES and hash functions have no proof of security from any complexity conjecture. Confidence comes from decades of public cryptanalysis. A worst-case 3-SAT algorithm does not change that analysis.
  • Encoding a cipher as SAT does not help much. Researchers do translate cryptographic problems into SAT formulas, but those formulas have many more variables than the key has bits, and the claimed saving in the exponent is tiny at those sizes. Neither OpenAI nor the verification group claims any cryptographic consequence.
  • P vs NP is still open. If P were equal to NP, most public-key cryptography would be in serious trouble. A refutation of ETH does not imply that.

There is a real but narrow area where ETH matters. SETH, the Strong Exponential Time Hypothesis, implies ETH, so a correct refutation of ETH also refutes SETH. Many fine-grained complexity results, such as conditional lower bounds for edit distance or orthogonal vectors, were proved assuming SETH or ETH. They lose that justification and need re-examination, although some may still follow from other assumptions. A research field called fine-grained cryptography has proposed proofs of work and even key-exchange schemes whose security is argued from conjectures of this family. Those proposals are academic, they are not deployed in banks or national PKIs, and their status will be part of what researchers now re-check.

Cryptographers were already debating AI and maths before this release. In a Scientific American report from 15 October 2026 about OpenAI’s earlier 722-paper release, Johns Hopkins cryptographer Matthew Green is reported as putting about a 15% chance on losing confidence in today’s public-key algorithms (secondhand, from his social-media post as reported by the magazine). Coinbase’s Yehuda Lindell is quoted as writing that there is “no evidence whatsoever” of a breakthrough against the underlying problems. KU Leuven’s Bart Preneel told the magazine there is “no real reason to panic”. Those comments predate the ETH claim and are not about it. They show the sensible middle ground: no panic, but a growing reason to make cryptography easy to replace.

Crypto-agility checklist for Gulf and Egypt banks, fintechs and gov-tech

The right response to an AI-maths headline is the same as the right response to quantum risk: know where your cryptography is and make it replaceable. Saudi financial institutions already have a dated obligation. A SAMA circular on quantum computing risks (SAMA Rulebook) requires them to finish identifying and classifying all cryptographic assets by the end of Q4 2026, and to complete an enterprise quantum-risk assessment with action plans by the end of Q1 2027. Here is the checklist we use with clients in Riyadh, Dubai and Cairo:

  • 1. Make no panic changes. Do not rotate keys, switch algorithms or rush a vendor patch because of the ETH headline. Rushed migrations cause outages and new bugs. Green warned that a botched upgrade can itself leave systems insecure.
  • 2. Build a cryptographic inventory (CBOM). List every place you use cryptography: TLS endpoints and certificates, mobile certificate pinning, HSMs and key-management, JWT and API signing, card and 3-D Secure flows, database and backup encryption, VPNs, code signing, e-invoicing stamps (ZATCA and the UAE’s ASP model) and third-party SDKs. Record the algorithm, key size, owner, data sensitivity and how long the data must stay secret.
  • 3. Classify by data lifetime. Data that must stay confidential for 10+ years, such as identity, health and banking records, is the priority for post-quantum migration, because of “harvest now, decrypt later” risk. Short-lived session data is lower priority.
  • 4. Follow the standards, not the headlines. NIST finalised its first post-quantum standards (FIPS 203 ML-KEM, FIPS 204 ML-DSA, FIPS 205 SLH-DSA) in August 2024. Under its draft transition plan (IR 8547), quantum-vulnerable algorithms are deprecated and removed from NIST standards by 2035, with high-risk systems moving much earlier (NIST PQC). NIST’s white paper on crypto agility (CSWP 39 update 1) is a practical design guide.
  • 5. Track the Saudi NCA standard. The NCA’s National Cryptographic Standards (2020) deferred post-quantum algorithms to later versions. From 10 to 25 December 2025 the NCA consulted on an update, NCS-2:2025, that adds post-quantum algorithms (ML-KEM, ML-DSA, SLH-DSA and Classic McEliece), random-number generation and quantum key distribution, and that would require post-quantum algorithms to be used together with classical ones (NCA announcement). We could not confirm a final published version on 27 October 2026. Check the NCA site before you lock your roadmap.
  • 6. UAE and Egypt teams: follow your regulator’s current guidance (CBUAE and the UAE Cybersecurity Council in the UAE, the Central Bank of Egypt for Egyptian banks and fintechs). We found no dated, public post-quantum deadline for either country, so use NIST’s timeline and your parent bank’s or card scheme’s requirements as the baseline.
  • 7. Design for swap-ability. Keep algorithms in configuration, not hard-coded. Use maintained libraries rather than home-grown code. Test hybrid post-quantum key exchange where your TLS stack and CDN support it, and make sure mobile apps can receive new pins and certificates without a forced store release.
  • 8. Put it in vendor contracts. Ask core-banking, payment, HSM and identity vendors for their post-quantum and crypto-agility roadmap, with dates, as part of your next renewal.

How to verify AI-produced proofs and code before you trust them

The OpenAI episode is also a lesson for any team shipping AI-generated work. Lean is a proof assistant: if Lean accepts a proof, the formal statement follows from the definitions and axioms used. Three things still need human checking, and the same three apply to AI-written code:

  • Does the formal statement say what you think it says? A perfect proof of the wrong statement is worthless. Reviewers of the ETH claim will compare the Lean theorem with the standard definition of ETH, encodings and machine model included. OpenAI’s own scope note already shows the Lean bound is weaker than the paper’s.
  • What does the proof depend on? Check for unproved placeholders (sorry), extra axioms and custom definitions. OpenAI’s repository uses “Comparator” challenge files so outsiders can check the formal statement independently.
  • Can someone else reproduce it? Pin the Lean and Mathlib versions, build from a clean checkout, and have reviewers who did not write the prompt read the argument.
  • For AI-written code, apply the same rule: tests and property-based tests written separately from the generated code, static analysis, dependency checks, and human review for anything touching money, identity or cryptography. Formal verification is worth the cost for parsers, payment logic and crypto wrappers. As our PHP php2shell patch guide and Plugin4Shell coding-agent analysis show, AI is now finding flaws faster than teams patch them, which makes independent review more important, not less.

OpenAI’s own record shows why unformalized results need caution. Its repository says only about 42% of top-line results have Lean formalizations, and warns that “some of the unformalized results could have issues”. On 7 October OpenAI withdrew three manuscripts after a sign error invalidated an argument, and revised 14 others (history). That came after the September Navier–Stokes episode we covered in our analysis of OpenAI’s maths claim, where the claim remained independently unverified. Each time, the lab published corrections in the open, but the headlines ran ahead of the checking.

What to watch next

  • The ETH group’s first readout: whether the Lean statement matches standard ETH and whether the counting algorithm holds up. The group says it will share findings throughout and plans a public form and blog for contributions.
  • The physics write-up from the Gross group, and whether any AI artifacts are released.
  • Independent reviews of the local-smoothing paper by harmonic analysts, who were left to organise their own effort.
  • Any cryptography-specific claim. If one appears, it will come with a paper and named reviewers. Treat social-media claims of “broken RSA” as false until then.

For product teams, the practical takeaway does not change with the outcome. Keep your cryptography inventoried and replaceable, and treat AI-generated proofs and code as drafts that need independent checking. Our GPT-6.1 Terra guide covers the OpenAI model that launched the same day, if you are weighing which models to put into production.

Frequently asked questions

What exactly did OpenAI claim about the Exponential Time Hypothesis, and what has been verified?

On 26 October 2026 OpenAI said an internal, unreleased model found a disproof of the Exponential Time Hypothesis (ETH) on 16 October and that the result was formalized in the Lean proof assistant on 17 October. The AI-written paper describes a deterministic algorithm that counts the satisfying assignments of k-CNF formulas in subexponential time and polynomial space. Lean checks that a proof is correct for its formal statement. It does not, on its own, mean that experts accept that the statement captures ETH or that the paper is right in every detail. The verification group led by Russell Impagliazzo, Ramamohan Paturi and Ryan Williams says its involvement should not be taken as certification. As of 27 October 2026, the claim is under independent review.

Does disproving the Exponential Time Hypothesis mean P = NP?

No. ETH says 3-SAT needs time 2 to the power of a constant times n. The claimed algorithm runs in roughly 2 to the power of n divided by the square root of log n, as Ryan Williams summarised it. That is faster than any fixed exponential, but still enormously slower than polynomial time. P versus NP stays open, and OpenAI itself says practical algorithms ‘will require significant further research’.

Does the OpenAI ETH result break RSA, ECC, AES, HTTPS, banking apps or Bitcoin?

No one, including OpenAI and the ETH verification group, has claimed that it does. RSA rests on the hardness of factoring, ECC on the elliptic-curve discrete logarithm problem, and AES on decades of cryptanalysis. None of them rests on ETH. Factoring already has a known subexponential classical algorithm, the number field sieve, and RSA key sizes are chosen with that in mind. ETH matters to some fine-grained complexity results and to a research area called fine-grained cryptography, which experts will now re-examine. Those schemes are not what protects your banking app. Do not rotate keys or change production systems because of this headline.

Did OpenAI solve the Yang–Mills Millennium Prize problem?

Not as the Clay Mathematics Institute states it. OpenAI claims a rigorous existence proof for certain four-dimensional quantum field theories, including QCD, and as a subproblem the existence of pure Yang–Mills theory, which it calls ‘part of’ the Clay problem. The Clay problem asks for existence and a mass gap, and OpenAI’s post does not claim the mass gap. The physics material has not been released. A group led by Nobel laureate David Gross is writing it up first.

Will SAT solvers, route planning, scheduling or chip-verification tools get faster now?

Not soon, and not automatically. Industrial SAT solvers already handle many large real-world instances well, and ETH is a worst-case statement about the hardest inputs. OpenAI says turning the theory into practical improvements needs significant further research, and the claimed speed-up in the exponent is very small for real input sizes. The near-term effect is on theory: hundreds of conditional lower bounds that assumed ETH have to be re-checked.

Related reading

Sources