// transaction detail · resource

secp256k1 Master Reference: Security Status, Open Problems, and the October 2026 AI-Math Wave

Prepared: 2026-10-10
Status: Consolidated master document — supersedes nothing, summarizes everything. Single-source reference for the current security picture, the complete open-problems inventory, and the news context.
Audience: Casual math follower (study-guide level: The Curve That Powers Bitcoin, clock arithmetic → Schnorr signatures)
Companion documents: Critical security review · Papers and hypothetical breaks · Ranked attack agenda · secp256k1 podcast notes · Matrix-multiplication podcast notes

0. Executive summary — ten sentences

  1. No one has broken secp256k1 by any means. No classical algorithm, no quantum computer, no AI result — the ~2^128 classical work estimate stands.
  2. The known weak-curve diseases are excluded for this curve, much of it machine-checked in 2026 (prime order, non-anomalous, huge embedding degree, prime field, twist-safe). A Lean/Mathlib development verified these plus primality, exact order, the GLV endomorphism, and Shoup's generic lower bound — while describing itself as "an honest no-go map," not a proof of security.
  3. The entire classical attack surface is one gap: Shoup (1997) proved blind, "generic" attackers can't beat ~√n; no theorem covers attackers who read the coordinates. Forty years of failed attempts, no impossibility proof.
  4. The open problems are named and published, not folklore: Semaev's prime-field point-decomposition speed (open 21 years), the initial-minors Conjecture A (2021), CM/GLV asymptotic exploitation, lifting height bounds, isogeny weak-cousin existence, GRH.
  5. Formal verification is "defensive only" so far — as an observed fact, not a law. Everything machine-checked to date (fiat-crypto, safegcd, scalar-mul, the Lean ECDLP project) removes ways to be wrong; none finds new ones. Proving security would imply one-way functions exist — stronger than P ≠ NP — while breaking needs only one constructive algorithm. Three "doors" exist for formal methods to go on offense.
  6. The news week: OpenAI released ~719 maintained math manuscripts (Oct 6) — none cryptographic (Aaronson: "conspicuous by its absence"), but including a claimed landmark ω ≤ 9/4 in matrix multiplication. Justin Drake (Oct 7) urged the industry to "calmly begin planning for 'bunker mode'" — a prior, not a claim; he explicitly states no known attack. Reactions split (Lindell: "really bad take"; Qureshi: "very sober call"; Buterin: don't scramble).
  7. The matrix-multiplication parallel is the evidence in the Drake debate: a machine claimed to leap past a proven 50-year-old barrier in algebra, Lean-formalized but unrefereed, with an AI-written follow-up paper five days later. Methodology, not the exponent, is the signal for crypto.
  8. Quantum remains the only proven-in-principle break: 2026 resource estimates fell to ~835–1,450 logical qubits (IonQ full-stack: 19,397 physical, ~26 days); today's machines have ~100 logical. Migration target ~2029; the bottleneck is governance, not algorithms.
  9. Practical damage to date has been implementation failures, not math: 302 Bitcoin keys recovered from defective nonces (2019 study); PS3, Android, Blockchain.info nonce disasters. Modern deterministic nonces (RFC 6979, BIP340) remove that class.
  10. The honest one-liner: the open problems have names, they sit in published papers, and for the first time the things reading them include machines that never get tired. That is the whole story of this month.

1. The news week, in exact detail

Timeline

Why everyone can be right

No attack exists — the argument is over priors: how much to update when machines start producing landmark-class proofs in algebra. Evidence cited by each side: 40 years of failed attacks (the skeptics' data) vs. the OpenAI release's shape (the worriers' data). Both are reading the same facts.

2. The mathematics in plain language (study-guide level)

The two clocks. All arithmetic happens modulo a 78-digit prime, p = 2^256 − 2^32 − 977 (guide Ch 1–3: clock arithmetic; close to a power of 2 for fast reduction). Secret keys and signature scalars live modulo a different 256-bit prime, n — the curve's group order. Coordinates mod p; scalars mod n. (ECDSA's conversion between them is where its security proofs get headaches.)

The curve. y² = x³ + 7 over the prime clock: ~2^256 points forming a group under the chord-and-tangent rule (guide Ch 6–7). Group order is itself prime, cofactor 1 — no small subgroups, so Pohlig–Hellman is excluded by construction.

The one-way street (guide §5.6). Private key d → public key Q = dG by double-and-add: milliseconds. Backward — the elliptic-curve discrete logarithm problem (ECDLP) — believed to need ~2^128 group operations: the guide's ">10^19 years." Everything in Bitcoin sits on that asymmetry (guide §5.5, Jonas Nick box: if anyone finds an efficient ECDLP algorithm, ECDSA, Schnorr, and MuSig2 break simultaneously).

The curve's quirk. j-invariant 0 — an extra order-3 endomorphism (GLV). Honest computation uses it (faster point multiplication); attackers get a constant-factor discount only. SafeCurves flags small CM discriminant as a "keep an eye," not a wound. Satoshi's parameter choice over NIST P-256 (guide §8.3): no unexplained seed — "nothing up my sleeve," with the nuance that SafeCurves grades it "somewhat rigid," not fully explained.

Why ECC keys are small. 128-bit security: RSA needs 3072 bits, ECC 256 (guide §5.5 table). That 12× advantage exists because index calculus never landed on prime-field curves — the whole story of Section 5.

3. What is proven, ruled out, and assumed

Category Items Status
Ruled out for this curve Pohlig–Hellman (n prime) · anomalous/Smart (order ≠ p) · MOV/Frey–Rück pairing transfer (embedding degree (n−1)/6) · Weil descent/GHS (prime field, no subfield) · small-subgroup (cofactor 1) · twist attacks (lift_x rejects non-residues) Established; the attack-exclusion layer machine-checked in Lean (2026)
Proven — defensive Shoup's generic Ω(√n) bound (1997; Lean-checked core 2026) · Schnorr SUF-CMA in ROM under ECDLP (Pointcheval–Stern; Kiltz–Masny–Pan; provably non-tight — Seurin) · key-prefixing security · x-only keys lose nothing · ECDSA in GGM+ROM (Brown) and via bijective-RO conversion idealization (Fersch–Kiltz–Poettering); one-per-message (FKP17); proof barriers (Hartmann–Kiltz 2023) Conditional theorems — every security proof assumes ECDLP hardness or idealizes a component
Assumed — never proven ECDLP hardness itself (proving it would imply one-way functions exist, stronger than P ≠ NP) · SHA-256's collision/preimage/pseudorandomness properties The foundation is an assumption; 40 years of attack is the evidence
Formally verified implementations fiat-crypto field arithmetic (PR open) · Blockstream safegcd Coq proof (2024) · scalar-mul Rocq/VST proof (2026) · KeyAI Lean ECDLP project (primality certs, exact order, GLV, S₃/S₄, exclusions, generic bound) Defensive: each removes a way to be wrong; none finds new ones

4. The complexity lens: why "128 bits"

Big O in one line: how work grows as the problem grows, constants ignored. Linear algebra is the gold standard of fast: solving n equations ~n³ ops — milliseconds at n = 1000. Exponential: each added key bit doubles work. At b = 256 bits, birthday-style search is 2^128 ≈ 3.4×10^38 operations ≈ the guide's >10^19 years at a trillion ops/second. Every 8 key bits ≈ 16× work.

The subtlety that matters: "polynomial in what?" √N is polynomially bounded in the group order N but exponential in the bit length b. Cryptographic "polynomial time" means polynomial in b. And subexponential (index calculus, the number-field sieve: work like exp((log N)^{1/3}…)) is the middle world — why RSA-3072 only matches ECC-256. The whole attack story is dragging the ECDLP out of the exponential column and into subexponential or polynomial:

Complete classical cost Work level Reduction from ~128 bits
2^128 128 bits none
2^112 112 bits 16 bits
2^96 96 bits 32 bits
2^80 80 bits 48 bits
2^64 64 bits 64 bits

(Continued in §5.)

5. The complete open-problems inventory

Tier 1 — Offensive: a proof here weakens Bitcoin

Route 1 family — point-factoring (Semaev 2004):

Route 2 — the initial-minors line:

Route 3 — the curve's symmetry (CM/GLV):

Route 4 — lifting:

Route 5 — isogeny detours:

The umbrella gap:

Tier 2 — Defensive: a proof here strengthens Bitcoin

Tier 3 — Formalization tasks (the Lean workstream)

Tier 4 — Verification status (live items in the news)

6. The five routes in plain words

Route 1 — "Invent point-factoring." Index calculus broke the integers world by collecting coincidence-receipts among small primes and letting linear algebra finish. The guide's sentence — there is no notion of factoring a point — is the wall. Semaev (2004) built the receipt-detector: polynomials Sₘ that vanish exactly when m points sum to zero, turning "does this point split into factor-base points?" into a solvable equation. Over extension fields the fast version is proven (Gaudry, Diem); over Bitcoin's plain prime clock, solving is brutally expensive — the open problem. Stakes: 2^80–2^112.

Route 2 — "The zero-minor lottery ticket." Reduce the discrete log to finding a zero determinant ("zero minor") in a matrix built from curve points — proven equivalence. A k×k matrix has ~2^k minors (hopeless to enumerate), so Conjecture A proposes a small witness set. An effective polynomial version = polynomial-time discrete log = full break. The 2026 follow-up is the reality check: polynomial for fixed defect, but the defect must grow — currently no better than exhaustive search. Cleanest stated open conjecture in the field; best formalization target.

Route 3 — "Break the coupon." The j = 0 symmetry gives honest computation speed and attackers a constant-factor discount (lane-merging in the random walk). Open: is there an asymptotic trick hiding in the order-3 endomorphism? If found: a break specific to this curve family — which, for Bitcoin holders, is the same as a break.

Route 4 — "Go back up the chapters." The guide teaches the curve over ℝ (Ch 6) then mod p (Ch 7); this attack reverses the order — lift the scatter-plot problem to the smooth curve over ℚ, solve with two thousand years of tools, reduce back. Drowns in exponential "height" growth (Silverman et al.), but the bounds have soft edges and this curve's lifts are rich (2025 quantum evidence). Low probability, high payoff.

Route 5 — "Rob the branch office." Curves come in families joined by isogenies — translation dictionaries that carry the secret scalar across intact, so solving the log on any cousin solves it everywhere. But isogenous curves over the same field share the same point count, so every classic weakness is family-wide impossible; and (under GRH) the family is a fast-mixing expander — all doors equally strong, corridors short. Open prizes point both ways: prove GRH (defensive) or find an uncovered weak cousin (offensive). Contrast: SIDH fell in 2022 because its protocol published extra structure; secp256k1 publishes nothing but two points.

7. "Defensive only," spelled out — and the three doors

What a proof assistant is: a kernel checker — spell-checker for mathematics. You state a theorem exactly; the machine checks every step of the argument. It guarantees the argument is valid; it does not tell you what to write, whether the statement matters, or whether the assumptions hold. A green build means exactly what the statement says — nothing more.

Why everything formalized so far defends secp256k1: the artifacts (verified field arithmetic, safegcd, scalar multiplication, the Lean ECDLP no-go map) all verify things already believed. Each removes a way to be wrong; none finds new ways. Defensive-only — an observed fact, not a law of nature.

The deep asymmetry: proving security needs unconditional hardness — implying one-way functions exist, stronger than P ≠ NP, beyond current technique. Breaking needs one constructive algorithm plus a proof it runs fast. Insecurity is constructive; security is asymptomatic. You cannot prove no burglar will open your vault; you can prove this crowbar opens it.

The three doors to offense:

  1. The crowbar — AI + Lean discovers and proves an efficient algorithm for point-factoring or the initial-minors set. "Defensive only" flips overnight. This is Drake's fear in engineering terms: not a model predicting keys, but a model proving a theorem that is an algorithm.
  2. Break the proofs, not the math — find an error in a deployed scheme's security proof. 2026 precedent: an LLM cryptanalysis benchmark (CryptanalysisBench) found a genuine flaw in KINDI's published CCA proof and mounted a key-recovery attack on the SpoC cipher — weak NIST-candidate primitives, not secp256k1, but the mechanism is the point. Related: Hartmann–Kiltz show ECDSA's proof story has known soft spots.
  3. Sharpen the conjecture — formalizing folk conjectures precisely is often what makes them attackable or refutable. The initial-minors line is the live example: formalized with the efficiency quantifier explicit, experiments then hit the real object instead of the prose.

The subtle middle ground: AI provers compressed an 8-month human verification of curve25519-dalek to 11 hours for ~$467 (kernel-checked — soundness does not depend on the AI having guessed right). Every proof is checked; only the statements remain human judgment. The tools are neutral; the statements choose sides.

8. The parallel: matrix multiplication's 2026 breakthroughs

The race: cost of multiplying two n×n matrices = O(n^ω). Naive ω = 3; floor ω ≥ 2 (must write n² outputs); conjectured ω = 2.

Year Bound Who
1969 2.8074 Strassen (7 multiplications instead of 8)
1990 2.3755 Coppersmith–Winograd — record for 20 years
2010–2025 2.3737 → 2.371339 Stothers, V. Williams, Le Gall, Alman, Duan–Wu–Zhou — fourth-decimal era
Aug 2026 2.371177 Dupont et al. + AlphaEvolve — first record moved by an AI agent
Oct 6, 2026 2.37115924 Zadeh — with an exact, independently checkable certificate
Oct 2026 2.371055 (every field) OpenAI math release
Oct 2, 2026 ≤ 9/4 = 2.25 (over ℂ) OpenAI math release — new technique, unrefereed

Why it is impressive: every improvement since 1990 used the laser method on Coppersmith–Winograd tensors — and a 2015 barrier theorem (Ambainis–Filmus–Le Gall) proved that road cannot reach ~2.307. The 9/4 claim uses a different mechanism entirely (shared-leg entropy inequality on polynomial-multiplication tensors, feeding Strassen's asymptotic spectrum) — past the wall, by not using the road. In fraction-of-remaining-gap terms: 1990–2025 closed ~1.1% of the distance to ω = 2; the claim closes ~33% — a bigger single leap than Strassen's own discovery.

The caveats: complex numbers only; Lean-formalized but unrefereed (the release already retracted 3 manuscripts elsewhere); galactic constants — no computer will ever run it.

The pile-on: Zadeh's certified witness (Oct 6); Uznański's rectangular extension (Oct 7) with real consequences (shortest paths O(n^2.4999)) — a paper whose entire writeup was produced by GPT-6.1, human-vouched. Five days from claim to follow-up. Practical lane separately: AlphaEvolve's 4×4 in 48 multiplications (first char-0 improvement in 56 years), rationalized and optimized into shippable form (Sept 2026); Laderman's 1976 3×3 proven optimal by Lean-checked computer search.

Relevance to the Drake debate: ω appears by name in the ECDLP attack papers as the "linear algebra constant." A 2.25 threatens nothing directly (polynomial-speedup story; the 2^128 wall is exponential). But the methodology — AI + Lean producing landmark-class unrefereed proofs in algebra within days — is precisely the mechanism Drake fears pointed at discrete logs. Matrix multiplication was present in the OpenAI release; cryptography was absent. The crypto world watched a machine land in the neighboring field and asked the obvious question.

9. P vs NP and the complexity ladder

Plainly: P = problems where finding the answer is easy; NP = problems where checking a proposed answer is easy. P vs NP asks whether every easy-to-check problem is also easy-to-solve. Checking a finished Sudoku takes minutes; solving a blank one takes hours — is that gap a law of nature or our ignorance? Open since 1971 (Cook, Levin); a Clay Millennium problem; three proven proof-barriers have each ruled out whole styles of attack.

The crypto nuances (both directions matter):

  1. A break of Bitcoin would not settle P vs NP. Discrete log lives in NP ∩ co-NP — the "quiet middle class" where both yes- and no-answers are efficiently verifiable — not among the maximally-hard NP-complete problems. (If discrete log were NP-complete, it would imply NP = co-NP — a famous "too good to be true" signal.)
  2. Proving P ≠ NP would not secure Bitcoin. It only says some checkable problems are hard; it does not say this one is.
  3. The ladder runs strictly upward: P ≠ NP < one-way functions exist < "this specific curve is safe." Proving secp256k1 secure would climb past the first two rungs; nobody can currently climb the first.
  4. The precedent that keeps cryptographers humble: primality testing lived in that same quiet middle class for decades — until 2002 (Agrawal–Kayal–Saxena), when it was shown to be in P after all. The middle class has form.

10. Practicality scoreboard, as of 2026-10-10

Classical compute: No demonstrated break. Generic record ~117 bits (2016, months of FPGAs); secp256k1-specific record is a 129-bit interval (2025, GPU kangaroo) — only works on keys already restricted to a narrow range. Every 8 bits ≈ 16× work: the gap from 117-bit record to 2^128 is a factor of ~10^21 in work.

Implementation (the actual historical damage): The guide calls the ECDSA nonce "the most dangerous variable in all of cryptography" (Ch 10.5). PS3 (2010, one fixed nonce for every signature); Android wallets (2013, SecureRandom bug); Blockchain.info (2014). The 2019 "Biased Nonce Sense" study (Breitner–Heninger) scanned ~975M Bitcoin signatures and recovered 302 private keys from defective nonces, at ~38 CPU-years — real stolen keys, zero damage to the math. Modern wallets use deterministic nonces (RFC 6979: k = HMAC-SHA256(d, z); BIP340's tagged-hash variant), removing the RNG-failure class entirely.

AI + proofs: OpenAI's ~719 results — zero cryptographic. CryptanalysisBench (2026): frontier LLMs produce novel attacks on weak/scaled-down primitives (SpoC key recovery; KINDI proof flaw) — not on secp256k1-strength objects. CryptoProver: 8-month human verification of curve25519-dalek compressed to 11.4 hours for ~$467. CipherBank (ACL 2025): classical ciphers only; the "0% on modern crypto" claim in circulation misstates its scope.

Quantum (the proven-in-principle threat): 2026 was a resource-estimate arms race. The number that matters is logical (error-corrected) qubits:

Threat ranking, honestly stated: implementation bugs (live now), quantum-in-years, AI-math as the wildcard that could reorder the list.

11. How to judge the next claim

The five-question checklist:

  1. Exact target? Full-strength secp256k1 key, a toy curve, or a key known to live in a small range? (The 129-bit kangaroo record is not a break of real keys.)
  2. What's broken? The curve math, a scheme's security proof, an implementation, or a nonce? Different blast radii.
  3. Full cost, including success probability? "Polynomial" can still mean 2^128 at 256 bits; the 2026 initial-minors paper is the cautionary tale (polynomial for fixed defect; the defect must grow).
  4. Checked against what? Lean-kernel-checked? Refereed? Independently reproduced? (OpenAI's drop: Lean-checked statements, unrefereed, 3 retracted.)
  5. Who says so, and who gains? Matters more, not less, when results are withheld.

Applied to this week: Drake's warning passes #1 (correct target: exposed public keys), fails #3 as a claim (no algorithm, no cost — explicitly a prior, which he says himself). That is why it reads as either sober or FUD depending on your priors — it is a bet on Doors 1–3 of §7, not a report of a break.

Interpretation scale:

New result Appropriate reading
Machine-checked primality, order, group-law fact Better assurance of foundational facts; not an attack
Correctness proof for a library routine Better assurance for that routine
Improved generic-algorithm arithmetic (e.g., the 2026 EDS/BSGS work) Concrete progress; constant-factor, not asymptotic collapse
Polynomial identity or small-instance experiment Research seed; cryptographic scaling unestablished
A valid weakness in a signature-security assumption Reassess the affected scheme; check whether an efficient attack follows
Independently validated practical method for full-strength public-key recovery A serious break of the curve-based foundation
Credible large quantum-resource reduction Changed planning assumptions; not a hardware demonstration

12. What holders should actually do

13. Study-guide cross-reference

Master-document section Guide material
§2 (the math) Prologue; Ch 1–3 (clock → prime field); Ch 4 (groups); Ch 6–7 (curves, Hasse, scatter plot); Ch 8 (six parameters, nothing-up-my-sleeve); Ch 9 (key generation, double-and-add, ECDLP, address derivation)
§3–4 (proven/complexity) Ch 5 entire — §5.3 rho, §5.5 "Why the ECDLP Is Harder" (the factoring-a-point table), §5.6 one-way diagram (>10^19 years)
§5 Route 1 Extension of §5.5: Semaev's program is the attempt to invent point-factoring
§5 Route 4 Ch 6 → Ch 7 taught in reverse (lifting)
§7 (defensive only) Epilogue: "formal verification is being applied to the libsecp256k1 codebase itself"; §8.3 Steiner transparency box
§10 (scoreboard) Ch 10.5 nonce catastrophe table; §10.6 RFC 6979 (k = HMAC-SHA256(d, z))
Throughout Guide's anchor sentence (§5.5): "Elliptic curve points have no such structure — there is no notion of 'factoring' a point."

14. References

News week: CoinDesk (Oct 8) https://www.coindesk.com/tech/2026/10/08/bitcoin-and-ether-holders-urged-to-prepare-bunker-mode-against-possible-ai-attacks · The Block (Oct 7) https://www.theblock.co/news/ecosystems/2026-10-07-ethereum-researcher-justin-drake-bunker-mode-planning-private-key-recovery-risk-417954 · Unchained/Yahoo (Oct 8, reactions) https://tech.yahoo.com/ai/articles/ethereum-researcher-bunker-mode-call-104509255.html · Galaxy (Oct 9) https://www.galaxy.com/insights/research/openai-math-ai-ecdsa-crypto-security · DiggingBeagle (Oct 8) https://diggingbeagle.com/articles/ai-math-wallet-private-keys-risk-vs-evidence/

Classical cryptanalysis: Semaev 2004 https://eprint.iacr.org/2004/031 · Galbraith–Gaudry survey https://eprint.iacr.org/2015/1022 · Amadori–Pintore–Sala https://eprint.iacr.org/2017/609 · McGuire–Mueller https://eprint.iacr.org/2017/1262 · Huang–Kosters–Yeo https://eprint.iacr.org/2015/573 · Yokoyama et al. (J. Math. Cryptol. 2020) https://www.degruyterbrill.com/document/doi/10.1515/jmc-2019-0029/html · Caminata–Gorla https://eprint.iacr.org/2021/1611

Initial minors: jGCC 2021 https://arxiv.org/abs/2005.05039 · 2023 https://arxiv.org/abs/2310.04132 · Exp. Math. 2025 https://doi.org/10.1080/10586458.2025.2525844 · 2026 https://arxiv.org/abs/2607.09814

Security proofs & barriers: Shoup 1997 https://link.springer.com/chapter/10.1007/3-540-69053-0_18 · Kiltz–Masny–Pan https://eprint.iacr.org/2016/191 · Seurin https://eprint.iacr.org/2012/029 · Fersch–Kiltz–Poettering https://dl.acm.org/doi/10.1145/2976749.2978413 and https://eprint.iacr.org/2017/890 · Hartmann–Kiltz https://eprint.iacr.org/2023/914

Formal verification: KeyAI Lean ECDLP https://github.com/KeyAIGit/ecdlp-lean-verification · Blockstream safegcd https://blog.blockstream.com/formal-verification-of-the-safegcd-implementation/ · scalar-mul https://remix7531.com/post/formal_verification_secp256k1_scalar_mul/ · CryptoProver https://arxiv.org/abs/2608.00965 · CryptanalysisBench https://arxiv.org/abs/2607.18538 · SafeCurves https://safecurves.cr.yp.to/

Isogenies & lifting: Jao–Miller–Venkatesan https://eprint.iacr.org/2004/312 · Castryck–Decru (SIDH break) https://eprint.iacr.org/2022/975 · Barbulescu–Barcau–Pasol https://eprint.iacr.org/2024/1758 and LATINCRYPT 2025 https://link.springer.com/chapter/10.1007/978-3-032-06754-8_9

Quantum: Google whitepaper https://eprint.iacr.org/2026/625 · Chevignard–Fouque–Schrottenloher https://eprint.iacr.org/2026/280 · IonQ https://eprint.iacr.org/2026/1916 and https://www.ionq.com/blog/the-first-full-stack-blueprint-for-breaking-256-bit-elliptic-curve-signatures · 835-logical analysis https://postquantum.com/security-pqc/ecc-secp256k1-835-logical-qubits/ · Brace for impact https://arxiv.org/abs/2508.14011

Matrix multiplication: AlphaEvolve/ω https://arxiv.org/abs/2608.16884 · OpenAI 9/4 family https://github.com/openai/math · Zadeh https://arxiv.org/html/2610.10593 · Uznański https://arxiv.org/html/2610.10494 · race table https://en.wikipedia.org/wiki/Computational_complexity_of_matrix_multiplication · Dumas et al. https://arxiv.org/pdf/2609.12027

Specifications: BIP340 https://bips.dev/340/ · BIP143 https://bips.dev/143/ · RFC 6979 https://www.rfc-editor.org/rfc/rfc6979.html