Two shocks, one message for cryptography
This week’s encryption story is not one breakthrough but two, and they should not be blurred into a single “crypto is broken” headline. On the AI side, OpenAI and Anthropic each said an internal model had refuted the Exponential Time Hypothesis, or ETH, a long-standing assumption about the cost of solving 3-SAT and related problems . On the quantum side, Alice & Bob published a detailed resource estimate claiming that RSA-2048 could be factored with 22,593 physical cat qubits in 3.14 days under its stated hardware assumptions .
The common thread is hardness. Modern security depends on a practical gap between what is easy for a legitimate user and what is infeasible for an attacker. ETH is not the same thing as RSA, elliptic-curve cryptography or AES. But it has served as a deep organizing assumption for theoretical computer science, and its alleged failure forces researchers to recheck many conditional hardness results . Alice & Bob’s estimate is narrower and more operational: it addresses Shor’s algorithm against public-key systems on a specific fault-tolerant quantum architecture .
The immediate conclusion is therefore cautious but serious: no one should claim that the internet’s encryption failed overnight, yet no security leader should treat these announcements as academic theater.
What OpenAI and Anthropic say they found
ETH, first proposed by Russell Impagliazzo, Ramamohan Paturi and Francis Zane, says that 3-SAT cannot be solved in subexponential time as the number of variables grows . That assumption is stronger and more specific than the popular belief that P does not equal NP, but it has become a workhorse: researchers use it to prove that many algorithms cannot be dramatically improved unless ETH is false .
According to recent reporting, OpenAI announced a deterministic algorithm that counts satisfying assignments for these formulas in subexponential time while using polynomial memory . Anthropic followed with a paper credited to Claude, “A 2^o(n) Time Algorithm for 3-SAT,” and its own Lean formalization; the Anthropic paper reportedly says an internal Claude research model found the core algorithm on October 16 “with 14M output tokens and no human input” .
The important word is “claimed.” Control Plane reports that both labs released Lean-checked proofs, but also that the researchers organizing outside review of OpenAI’s claim have not certified the result . TechCrunch similarly describes an evolving release process in which computer scientists formed a working group, asked for proofs to be shared publicly, and sought broader community scrutiny rather than treating the announcement as the end of the matter .
That distinction matters for cryptography. A formal proof in Lean can reduce certain classes of logical error, but it does not automatically produce a practical exploit, a deployable solver, or a drop-in attack against TLS, blockchains or enterprise key infrastructure. Even if ETH is false, the algorithmic improvement may be asymptotic: huge in theory, irrelevant at real-world input sizes until further work changes the constants, implementation path or target problem.
Why cryptographers still care
The danger is not that an AI model has instantly learned to steal private keys. The danger is that a familiar map of computational difficulty may have a new coastline. WIRED quoted researchers saying the result could affect the cryptography underpinning web security, while noting that the specific ETH claim does not directly break cryptography . That is the right balance.
Cryptosystems rest on particular assumptions. RSA depends on the hardness of factoring large integers for classical computers. Elliptic-curve schemes depend on the hardness of discrete logarithms in elliptic-curve groups. Symmetric cryptography such as AES is analyzed differently again. ETH lives in complexity theory around satisfiability and reductions; it is not a universal master key.
But cryptography is not isolated from complexity theory. If AI-assisted mathematics starts finding non-obvious algorithms for problems believed to be hard, the security community has to ask sharper questions: Which reductions were only conditional? Which protocols rely on hardness assumptions adjacent to SAT-like problems? Which “infeasible” attack estimates are really just inherited confidence from old complexity intuitions?
The practical task is triage. Security teams should not rip out every cryptosystem because of ETH. They should ask vendors and internal cryptographers which deployed schemes depend on assumptions that could be weakened by subexponential algorithms, and whether any post-quantum candidates in use or under evaluation need fresh review.
Alice & Bob puts a number on RSA’s quantum risk
Alice & Bob’s announcement is easier for boards and CISOs to grasp because it turns the quantum threat into an engineering target. In its own blog, the company says it is publishing a resource estimate of about 23,000 physical qubits and about three days to break RSA-2048 on its cat-qubit architecture . The corresponding IACR ePrint entry gives the more precise figure: factoring RSA-2048 would require about 23,000 cat qubits and 3.14 days under assumptions including a 1 microsecond error-correction cycle, a 10 microsecond reaction time, circuit-level phase-flip noise probability of 5 × 10^-4 and no bit-flips .
The same paper estimates that solving ECDLP on secp256k1 would require at most 30,000 cat qubits and about one hour, and it proposes FFDLP-512 as an intermediate benchmark needing about 6,700 cat qubits and 21 minutes . The Quantum Insider reports the RSA-2048 headline as 22,593 physical cat qubits and 3.14 days, and notes that the elliptic-curve estimate is 29,588 physical qubits and 61.8 minutes .
This is not a claim that Alice & Bob has built such a machine. It is a resource estimate, not a live cryptanalytic demonstration. But it is still significant because quantum risk has often been communicated in vague terms: “a sufficiently large quantum computer” will someday break RSA and ECC. The new number gives planners something more concrete to track.
Why 22,593 qubits does not mean “safe until 22,592”
The number is not a universal countdown clock. It depends on Alice & Bob’s architecture, cat qubits, LDPC-cat codes, compilation choices, error rates, reaction times and assumptions about bit-flips . A different architecture could need more qubits, fewer qubits, longer runtime or shorter runtime. Alice & Bob itself notes that resource estimates for Shor’s algorithm have fallen steeply, from roughly 20 million physical qubits in earlier estimates to below one million and now to around 23,000 in its latest cat-qubit work .
The strategic point is the trend. Alice & Bob says the road is getting shorter from both ends: algorithms and compilation are improving, while quantum hardware and error correction are also advancing . The company’s conclusion is predictable but reasonable: migration takes years, and organizations should not wait until a cryptographically relevant quantum computer already exists before replacing vulnerable public-key systems .
For governments and enterprises, the exposed area is well known: RSA key exchange, RSA signatures, ECDH, ECDSA and other schemes based on factoring or discrete logarithms. Data with long confidentiality lifetimes is especially sensitive because attackers can harvest encrypted traffic now and decrypt it later if quantum capability arrives.
The action plan
The combined lesson from OpenAI, Anthropic and Alice & Bob is not panic. It is crypto-agility.
First, build or refresh a cryptographic inventory: certificates, VPNs, code-signing systems, payment links, firmware updates, identity infrastructure, cloud key-management settings and embedded devices. Second, classify exposure by algorithm and data lifetime. RSA and elliptic-curve systems deserve the closest quantum migration plan; schemes whose security assumptions are tied to SAT-like hardness deserve a separate theoretical review. Third, require vendors to disclose post-quantum road maps, hybrid modes and rollback options.
Finally, treat AI-assisted proof and quantum resource estimation as early-warning systems. The ETH claim needs independent scrutiny, and Alice & Bob’s RSA estimate is still conditional on a machine that does not yet exist at that scale. But both developments point in the same direction: assumptions are becoming more testable, timelines are becoming more concrete, and encryption planning can no longer rely on vague comfort about “hard problems.”
Comments
Be the first to comment.