1# WP34 — Stage 1 structured literature database2# Every `source` is a key in paper/references.bib (all verified 2026-11-01 via Crossref / IACR ePrint /3# arXiv / DOI / official standard URL). Formulas are plain text. `notes` records caveats and how the4# item will be used by the discovery pipeline.56theorems:7 - id: T018 statement: >9 Hasse bound. For an elliptic curve E over F_q, |#E(F_q) - (q + 1)| <= 2*sqrt(q); equivalently10 the Frobenius trace t satisfies |t| <= 2 sqrt(q).11 source: hasse1936theorie12 notes: >13 Modern statement and proof in silverman2009arithmetic (Thm. V.1.1) and washington2008elliptic (Thm. 4.2). For secp256k1 n is prime and the cofactor is 1 (certicom2010sec2).14 - id: T0215 statement: >16 Group structure. E(F_q) is isomorphic to Z/n1 x Z/n2 with n2 | n1 and n2 | (q - 1); in particular17 E(F_q) is cyclic or a product of two cyclic groups.18 source: washington2008elliptic19 notes: >20 Also silverman2009arithmetic III.6 / V.1. Pohlig-Hellman (A08) applies to the subgroup structure.21 - id: T0322 statement: >23 Deuring / CM theory. End(E) over the algebraic closure is Z, an order in an imaginary quadratic24 field (ordinary case) or an order in a quaternion algebra (supersingular). For secp256k125 (j = 0, p = 1 mod 3) End(E) contains Z[omega], omega a primitive cube root of unity, giving the26 order-6 automorphism group and the endomorphism phi(x, y) = (beta x, y) with beta^3 = 1 in F_p.27 source: deuring1941typen28 notes: >29 Operational consequences in gallant2001faster and wiener1999faster. CM discriminant -3.30 - id: T0431 statement: >32 Schoof's algorithm counts #E(F_q) deterministically in O(log^8 q) bit operations by computing the33 Frobenius trace modulo small primes l and recombining by CRT; SEA improvements (Elkies, Atkin)34 lower this to O~(log^4 q) heuristically.35 source: schoof1985elliptic36 notes: >37 SEA described in schoof1995counting. Used to validate synthetic-curve orders in the experiments.38 - id: T0539 statement: >40 Generic lower bound (Shoup 1997, Nechaev 1994). Any generic algorithm that computes discrete41 logarithms in a cyclic group of prime order p with probability >= 1/2 performs Omega(sqrt(p))42 group operations; the same bound holds for the Diffie-Hellman problems.43 source: shoup1997lower44 notes: >45 Nechaev proved the deterministic case (nechaev1994complexity). The bound is for the generic (black-box) model only; it says nothing about algorithms that use the representation of the group (e.g. index calculus).46 - id: T0647 statement: >48 Random-mapping statistics (Flajolet-Odlyzko 1990, Harris 1960). For a random mapping on an49 n-element set, the expected rho length (tail + cycle) of a random starting point is50 sqrt(pi n / 2) (1 + o(1)); expected tail length and cycle length are each sqrt(pi n / 8).51 source: flajolet1990random52 notes: >53 harris1960probability gives the earlier distributional results. Baseline for all rho experiments; a true random mapping is the negative control (CONVENTIONS 5).54 - id: T0755 statement: >56 Preprocessing lower bound (Corrigan-Gibbs-Kogan 2018). Any generic discrete-log algorithm with an57 S-bit advice string, online time T and success probability eps in a group of prime order N58 satisfies S T^2 = Omega~(eps N); the bound is tight up to logarithmic factors.59 source: corrigangibbs2018discrete60 notes: >61 Matching upper bound (S T^2 = O~(N)) given by bernstein2013nonuniform (rho with precomputed distinguished points) and by lee2011generic. Relevant to the fixed-group setting of secp256k1.62 - id: T0863 statement: >64 Pohlig-Hellman. If the group order factors as prod p_i^{e_i}, a discrete logarithm reduces to65 sum_i e_i instances in groups of prime order p_i plus CRT; the cost is dominated by the largest66 prime factor: O(sum_i e_i (log n + sqrt(p_i))) group operations with rho or BSGS.67 source: pohlig1978improved68 notes: >69 secp256k1 has prime order n, so Pohlig-Hellman gives nothing; it matters for synthetic composite-order instances.70 - id: T0971 statement: >72 MOV / Frey-Rueck reduction. If n | q^k - 1 for small embedding degree k, the Weil (MOV) or Tate73 (Frey-Rueck) pairing maps the ECDLP in the order-n subgroup into the DLP in F_{q^k}^*, which has74 subexponential algorithms.75 source: menezes1993reducing76 notes: >77 Tate-pairing version in frey1994remark. For secp256k1 the embedding degree is astronomically large (checked in SafeCurves, bernstein2014safecurves); the reduction does not apply.78 - id: T1079 statement: >80 Anomalous-curve attack. If #E(F_p) = p (trace 1), the ECDLP is solvable in polynomial time by81 lifting to the p-adics / Fermat quotients (Semaev, Smart, Satoh-Araki, independently).82 source: smart1999discrete83 notes: >84 semaev1998evaluation and satoh1998fermat are the other two original sources. secp256k1 has n != p, so the attack does not apply.85 - id: T1186 statement: >87 Summation polynomials (Semaev 2004). For an elliptic curve E, there exist polynomials f_m in m88 variables of degree 2^{m-2} in each variable such that f_m(x_1, ..., x_m) = 0 iff there exist89 points P_i with x(P_i) = x_i and P_1 + ... + P_m = O.90 source: semaev2004summation91 notes: >92 Basis of index-calculus on elliptic curves; see T12 / N05 for why this fails over prime fields.93 - id: T1294 statement: >95 Index calculus on E(F_{q^n}) (Gaudry 2009, Diem 2011). For fixed n >= 2 and q -> infinity, Weil96 descent on summation polynomials solves the ECDLP in heuristic time O~(q^{2 - 2/n}); Diem proves97 subexponential complexity for families with n growing like sqrt(log q).98 source: gaudry2009index99 notes: >100 diem2011discrete gives the rigorous version. Requires an extension field: no analogue is known for prime fields (N05).101 - id: T13102 statement: >103 Forking lemma. From a forger that succeeds with probability eps against a Schnorr-type signature104 in the random-oracle model after q_h hash queries, one extracts the discrete logarithm with105 probability about eps^2 / q_h; hence Schnorr is EUF-CMA secure under the DLP in the ROM, with a106 loss factor q_h.107 source: pointcheval2000security108 notes: >109 General forking lemma (any algorithm) in bellare2006multi. Tightness discussed in T14.110 - id: T14111 statement: >112 Seurin 2012. In the ROM, any algebraic reduction from the DLP to Schnorr unforgeability must lose113 a factor close to q_h; the forking-lemma bound is essentially optimal, and the random-oracle114 assumption cannot be removed for the standard DL-based proof (building on Paillier-Vergnaud 2005).115 source: seurin2012exact116 notes: >117 paillier2005discrete shows DL-based signatures (including Schnorr and ECDSA-like schemes) cannot be proven equivalent to DL via algebraic reductions in the standard model under the one-more DL assumption.118 - id: T15119 statement: >120 ECDSA in the generic group model (Brown 2005). If the conversion function x(R) mod n is modelled121 via a generic group and the hash is collision-resistant (plus a 'almost-invertibility' condition122 on the conversion), ECDSA is existentially unforgeable.123 source: brown2005generic124 notes: >125 Also vaudenay2003security (DSA/ECDSA in the ROM-like 'generic' hash model). The generic group model is strong; it ignores the actual structure of secp256k1.126 - id: T16127 statement: >128 Fersch-Kiltz-Poettering 2016/2017. Modelling the conversion function f(R) = x(R) mod n as a129 bijective random oracle (and the hash as a random oracle), ECDSA is EUF-CMA secure under the130 DLP; without the bijective-RO idealisation one still gets one-per-message unforgeability for131 ECDSA and its variants under appropriate assumptions.132 source: fersch2016provable133 notes: >134 fersch2017one is the one-per-message result. Neither result covers the malleability (s, n - s) of ECDSA, which is inherent.135 - id: T17136 statement: >137 Groth-Shoup 2022. ECDSA remains secure in the generic group model when additive key derivation138 (BIP32-style tweaks pk + tG) and presignatures (R computed before the message) are used, with an139 explicit degradation bound; the proof is given in the GGM with a concrete hash assumption.140 source: groth2022security141 notes: >142 Relevant to Bitcoin derivation paths and threshold ECDSA; the result is in the GGM only.143 - id: T18144 statement: >145 Nonce leakage breaks ECDSA. Knowledge of a few bits of the nonce k for many signatures reduces key146 recovery to a hidden-number / closest-vector problem solvable by lattice reduction (Howgrave-Graham147 and Smart 2001); real-world biased nonces were exploited in cryptocurrencies (Breitner-Heninger148 2019); less than one bit of leakage suffices with enough signatures (LadderLeak 2020).149 source: howgravegraham2001lattice150 notes: >151 breitner2019biased, aldaya2020ladderleak (authors Aranha, Novaes, Takahashi, Tibouchi, Yarom), jancar2020minerva. Motivates deterministic nonces (pornin2013rfc6979, wuille2020bip340).152 - id: T19153 statement: >154 Merkle-Damgaard. If the compression function f is collision resistant and the padding encodes the155 message length (MD strengthening), the iterated hash H is collision resistant.156 source: merkle1989one157 notes: >158 damgard1989design is the independent proof. SHA-256 follows this construction (nist2015fips180) with 64-step compression on 512-bit blocks and 256-bit chaining value.159 - id: T20160 statement: >161 Tseitin transformation. Any Boolean circuit with m gates has an equisatisfiable CNF with O(m)162 clauses and O(m) auxiliary variables; this is the encoding used to turn reduced-step SHA-256 into163 SAT instances.164 source: tseitin1983complexity165 notes: >166 Used by mironov2006applications, nejati2017adaptive, alamgir2024sha256 and by Lean's bv_decide (boving2025interactive).167 - id: T21168 statement: >169 Shor 1997. On a quantum computer the discrete logarithm problem in any cyclic group with170 efficiently computable group law is solvable in polynomial time; resource estimates for171 256-bit prime-field ECDLP are about 2330 logical qubits and 1.26e11 Toffoli gates172 (Roetteler et al. 2017).173 source: shor1997polynomial174 notes: >175 roetteler2017quantum. Out of scope for the classical experiments; cited in the implications section.176177algorithms:178 - id: A01179 statement: >180 Baby-step giant-step (Shanks 1971). Deterministic, O(sqrt(n)) group operations and O(sqrt(n))181 memory; with m = ceil(sqrt(n)) baby steps and giant steps of size m.182 source: shanks1971class183 notes: >184 Interval and low-weight variants in bernstein2012two and stinson2002some. Memory makes it impractical beyond ~2^40 in practice but it is the exact-count baseline.185 - id: A02186 statement: >187 Pollard rho (1978). Iterate a pseudo-random walk x_{i+1} = f(x_i) on the group with a cycle-finding188 method; a collision x_i = x_j with distinct (a, b) representations yields the logarithm. Expected189 cost about sqrt(pi n / 2) group operations with O(1) memory when f behaves like a random mapping.190 source: pollard1978monte191 notes: >192 Cycle finding by Floyd (original) or Brent (brent1980improved, fewer function evaluations). The original 3-partition walk is not random enough (teske1998speeding).193 - id: A03194 statement: >195 Pollard kangaroo / lambda (1978, 2000). Two walks (tame, wild) with jumps of mean size about196 sqrt(w)/2 solve a logarithm known to lie in an interval of width w in about 2 sqrt(w) operations;197 the 2000 paper gives the refined 'monopoly' analysis and the parallel version.198 source: pollard2000kangaroos199 notes: >200 Interval DLP improvements with equivalence classes in galbraith2010interval (about 1.36 sqrt(w)) and the 'grumpy giants' BSGS variant in bernstein2012two.201 - id: A04202 statement: >203 r-adding walks (Teske 1998/2001). With r >= 20 random multipliers, the adding walk x -> x + M_{h(x)}204 behaves close to a random mapping and the rho cost approaches sqrt(pi n / 2); r = 3 is about205 30% slower; mixed adding/doubling walks also work.206 source: teske2001random207 notes: >208 teske1998speeding is the ANTS version. Partition count r is a free parameter for sensitivity analysis.209 - id: A05210 statement: >211 Parallel collision search with distinguished points (van Oorschot-Wiener 1999). m processors212 each run independent walks and report points with a distinguishing property (probability theta)213 to a central store; expected time sqrt(pi n / 2)/m + 1/theta per processor, i.e. linear214 speedup with memory about theta sqrt(pi n / 2) points.215 source: vanoorschot1999parallel216 notes: >217 Used by every ECDLP record since 2000 (bos2012solving, wenger2014solving, bernstein2016faster). The additive overhead 1/theta is the price of distinguished points.218 - id: A06219 statement: >220 Negation map. Iterating on classes {P, -P} halves the effective group size, giving an expected221 speedup of sqrt(2) for rho; it introduces fruitless 2-cycles (and longer cycles) that must be222 detected and escaped, costing a constant factor if handled carelessly.223 source: wiener1999faster224 notes: >225 bos2010negation quantified the fruitless-cycle overhead and reported practical speedups below sqrt(2); bernstein2011correct shows how to approach the full sqrt(2) with cheap cycle handling. Also gallant2000improving.226 - id: A07227 statement: >228 Automorphism speedup. If E has an efficiently computable automorphism group of order m acting on229 the order-n subgroup, rho on orbits gives an expected speedup of sqrt(m): sqrt(2 l) for Koblitz230 curves over F_{2^l} (Frobenius and negation), sqrt(6) for j = 0 curves such as secp256k1 (order-6231 group generated by (x, y) -> (beta x, -y)), sqrt(4) for j = 1728.232 source: duursma1999speeding233 notes: >234 Independently gallant2000improving and wiener1999faster. The sqrt(6) for secp256k1 is the only known structural advantage of its CM; it is a constant factor, not a change of exponent.235 - id: A08236 statement: >237 GLV scalar decomposition. For a curve with endomorphism phi acting as [lambda], write238 k = k1 + k2 lambda (mod n) with |k1|, |k2| about sqrt(n) via a short lattice basis; the scalar239 multiplication kP = k1 P + k2 phi(P) with simultaneous (Straus-Shamir) double-and-add roughly240 halves the number of doublings.241 source: gallant2001faster242 notes: >243 Bounds on |k1|, |k2| proven in sica2002analysis; generalised to a large class of curves (GLS) in galbraith2011endomorphisms (and galbraith2009endomorphisms). libsecp256k1 implements the split (wuille2013libsecp256k1, src/scalar_impl.h).244 - id: A09245 statement: >246 Multi-scalar multiplication. Straus (1964) / Shamir trick computes a1 P1 + ... + ak Pk with one247 shared doubling chain; Pippenger (1980) achieves about (l / log l)-type savings for many terms via248 bucket methods; interleaving with sliding windows (Moeller 2001) is the practical choice for249 k = 2 (ECDSA/Schnorr verification).250 source: straus1964addition251 notes: >252 pippenger1980evaluation, moller2001algorithms. Batch verification reduces to one large MSM (A11).253 - id: A10254 statement: >255 Coordinates and ladders. Mixed Jacobian/affine coordinates minimise field operations for256 double-and-add (Cohen-Miyaji-Ono 1998); Montgomery's x-only ladder (1987) and its Weierstrass257 adaptation (Brier-Joye 2002) give uniform, side-channel-resistant scalar multiplication.258 source: cohen1998efficient259 notes: >260 montgomery1987speeding, brier2002weierstrass. Generalised-Mersenne reduction for p = 2^256 - 2^32 - 977 follows solinas1999generalized. Timing attacks: kocher1996timing, brumley2011remote.261 - id: A11262 statement: >263 Batch verification. For Schnorr-type signatures, verifying N signatures reduces to one random264 linear combination sum a_i (s_i G - R_i - e_i P_i) = O with random 128-bit a_i, soundness error265 2^-128 (Naccache et al. 1994; Bellare-Garay-Rabin 1998); with Pippenger's MSM the cost per266 signature drops to a fraction of a single verification (Ed25519: roughly half, Bernstein et al. 2012).267 source: bellare1998fast268 notes: >269 naccache1994can, bernstein2012high. BIP340 (wuille2020bip340) is designed for batch verification; ECDSA is not batch-verifiable without recovering R (B04).270 - id: A12271 statement: >272 Schoof / SEA point counting (see T04) and Hasse-interval search are used to generate synthetic273 prime-order curves at 20-80 bits for the experiments.274 source: schoof1995counting275 notes: >276 Implementation gate: cross-check orders with two independent implementations (CONVENTIONS).277 - id: A13278 statement: >279 Tag tracing (Cheon-Hong-Kim 2012). In prime-field (multiplicative) groups, the rho walk can be280 advanced without full group multiplications by tracing a tag of the product, giving large281 constant-factor speedups; the technique is specific to F_p^* representation.282 source: cheon2012speeding283 notes: >284 No analogue for elliptic-curve groups is known (relevant to A4 of the mandate: representation-specific speedups).285 - id: A14286 statement: >287 Automated differential-characteristic search for SHA-2 (Mendel-Nad-Schlaeffer 2011/2013):288 guess-and-determine over generalised conditions with contradiction detection; the 2013 extension289 to longer local collisions produced 28-step practical, 31-step theoretical and 38-step290 semi-free-start collisions.291 source: mendel2011finding292 notes: >293 mendel2013improving; branching heuristics in eichlseder2014branching. SAT/MILP-based successors in li2024new, li2024first, zhang2026collision.294 - id: A15295 statement: >296 SAT-based cryptanalysis of hash functions (Mironov-Zhang 2006). Encode the step function with297 Tseitin and solve with CDCL; MapleCrypt adds adaptive restarts and CEGAR for inversion298 (Nejati et al. 2017); programmatic SAT with a CAS reproduces the 38-step SFS collision and finds299 pure-SAT collisions only up to 28 steps (Alamgir-Nejati-Bright 2024).300 source: mironov2006applications301 notes: >302 nejati2017adaptive, alamgir2024sha256. Solvers: biere2020cadical (Kissat), biere2024cadical (CaDiCaL 2.0), demoura2008z3 (SMT). Lean 4 bv_decide (boving2025interactive) checks LRAT proofs from CaDiCaL inside the kernel.303 - id: A16304 statement: >305 Biclique meet-in-the-middle preimages (Khovratovich-Rechberger-Savelieva 2012) extend the306 MITM preimage attacks of Aoki et al. 2009 from 43 to 45 steps of SHA-256 (hash) and 52 steps307 (compression function), all with complexity close to 2^256.308 source: khovratovich2012bicliques309 notes: >310 aoki2009preimages. These are not practical; they are the step-count frontier for preimages.311 - id: A17312 statement: >313 Deterministic nonces: RFC 6979 derives k = HMAC_DRBG(d, H(m)); BIP340 derives the nonce from a314 tagged hash of (auxiliary randomness xor d), P, m and uses x-only keys with even-y normalisation315 and challenge e = H_tag(r || P || m).316 source: pornin2013rfc6979317 notes: >318 wuille2020bip340; Taproot usage in wuille2020bip341. Both remove the nonce-reuse failure mode (T18) but not side channels.319320security_assumptions:321 - id: S01322 statement: >323 ECDLP on secp256k1: given G and Q = dG in the prime-order-n subgroup (n about 2^256), computing d324 requires about 2^128 group operations with the best known (generic) algorithms; the sqrt(6)325 automorphism gain lowers this to about 2^126.7 but no non-generic attack is known.326 source: galbraith2016recent327 notes: >328 Parameters from certicom2010sec2; curve analysis in bernstein2014safecurves. Baseline assumption for Axis A.329 - id: S02330 statement: >331 Random-oracle assumption on SHA-256 for Schnorr/BIP340 proofs; the challenge hash must be modelled332 as a random oracle, and Seurin shows this cannot be avoided for the DL-based reduction.333 source: seurin2012exact334 notes: >335 Links Axis B to Axis C: any structural regularity in SHA-256 would weaken the ROM idealisation before it weakens the DLP.336 - id: S03337 statement: >338 ECDSA security relies additionally on idealising the conversion function x(R) mod n339 (bijective random oracle or generic group); ECDSA is inherently malleable (s <-> n - s), which is340 why Bitcoin enforces low-s and why BIP340 Schnorr is preferred for new outputs.341 source: fersch2016provable342 notes: >343 brown2005generic, groth2022security. Malleability is a property, not a break.344 - id: S04345 statement: >346 Collision resistance of SHA-256 at the 2^128 level and preimage resistance at 2^256 (ideal-hash347 benchmarks); the Merkle-Damgaard structure makes these reduce to the compression function.348 source: nist2015fips180349 notes: >350 merkle1989one. Reduced-step results (E-series) do not threaten the 64-step function (gilbert2003security).351 - id: S05352 statement: >353 Generic-group model: lower bounds (T05) and ECDSA/presignature proofs (T15, T17) hold only for354 algorithms that ignore the encoding of group elements; secp256k1's special p and j = 0 are355 exactly the kind of structure the GGM cannot see.356 source: shoup1997lower357 notes: >358 This is the formal gap that Axis A probes: is there any representation-aware algorithm? See open problems.359 - id: S06360 statement: >361 Non-uniform / preprocessing security: with a 2^S precomputation table specific to secp256k1, the362 online ECDLP cost is about sqrt(n / S) (T07); a 2^80 table would give 2^88 online operations.363 The precomputation itself costs about 2^128 (bernstein2013nonuniform).364 source: bernstein2013nonuniform365 notes: >366 corrigangibbs2018discrete. Shows that 'free precomputation' claims need to account for the one-time cost; relevant to any claimed shortcut that amortises over many keys.367368complexity_bounds:369 - id: C01370 statement: >371 Expected rho iterations for a random mapping on n points: sqrt(pi n / 2) about 1.2533 sqrt(n);372 with the negation map sqrt(pi n / 4) about 0.886 sqrt(n); with the order-6 automorphism373 sqrt(pi n / 12) about 0.512 sqrt(n).374 source: flajolet1990random375 notes: >376 Second and third figures from wiener1999faster / duursma1999speeding assuming perfect handling of fruitless cycles (bernstein2011correct).377 - id: C02378 statement: >379 Parallel rho with m processors and distinguishing probability theta: expected time380 (sqrt(pi n / 2)/m + 1/theta) iterations per processor; memory about theta sqrt(pi n / 2) points.381 source: vanoorschot1999parallel382 notes: >383 The experiments must measure the 1/theta overhead and the linear scaling in m.384 - id: C03385 statement: >386 BSGS: sqrt(n) group operations and sqrt(n) stored points, deterministic; interval of width w:387 about 2 sqrt(w) for kangaroo (Pollard 2000), about 1.36 sqrt(w) with equivalence classes388 (Galbraith-Ruprai 2010), and BSGS variants in bernstein2012two.389 source: shanks1971class390 notes: >391 pollard2000kangaroos, galbraith2010interval.392 - id: C04393 statement: >394 Generic lower bound Omega(sqrt(p)) for prime p (T05); with S bits of preprocessing395 S T^2 = Omega~(N) (T07). Any claimed generic algorithm beating these is wrong.396 source: shoup1997lower397 notes: >398 corrigangibbs2018discrete. Serves as the falsification test for Axis A hypotheses that are generic.399 - id: C05400 statement: >401 Index calculus on E(F_{q^n}): O~(q^{2 - 2/n}) for fixed n (Gaudry), subexponential402 exp(O(log^{2/3} q)) type for suitable families (Diem); summation-polynomial systems over403 prime fields have no known subexponential solution (Petit-Quisquater analyse the Weil-descent404 systems and give heuristics for binary fields only).405 source: gaudry2009index406 notes: >407 diem2011discrete, petit2012elliptic, surveyed in galbraith2016recent.408 - id: C06409 statement: >410 GLV: with |k1|, |k2| < C sqrt(n) (explicit C from Sica-Ciet-Quisquater), the double-scalar411 computation needs about log2(n)/2 doublings instead of log2(n); the gain is a constant factor412 near 1.5-2 in practice.413 source: sica2002analysis414 notes: >415 gallant2001faster.416 - id: C07417 statement: >418 Batch verification of N Schnorr signatures: about one MSM of size 2N + 1 with 128-bit419 coefficients; with Pippenger the amortised cost per signature is roughly 1/2 to 1/3 of a single420 verification for N in the hundreds (Ed25519 measurements: about 134k cycles per signature in a421 batch of 64 versus 2.3x more individually, Bernstein et al. 2012).422 source: bernstein2012high423 notes: >424 bellare1998fast, pippenger1980evaluation. Axis B benchmark target.425 - id: C08426 statement: >427 SHA-256 collision frontier: practical 31 steps (1.2 h on 64 threads), theoretical 37 steps,428 semi-free-start practical 39 steps; preimage frontier 43 steps (2^254.9), 45 steps (biclique, hash),429 52 steps (biclique, compression function).430 source: li2024first431 notes: >432 zhang2026collision, li2024new, aoki2009preimages, khovratovich2012bicliques; full table in literature/records.md.433 - id: C09434 statement: >435 SAT-based SHA-256: pure CDCL finds collisions only up to 28 steps; with CAS guidance a 38-step436 semi-free-start collision is reproduced (Alamgir et al. 2024). Earlier SAT inversions reach only437 about 20-24 steps (Mironov-Zhang 2006; Nejati et al. 2017).438 source: alamgir2024sha256439 notes: >440 These numbers are the baseline for Axis C research question C4 (reproduce known results with automated search).441 - id: C10442 statement: >443 Quantum: polynomial time for ECDLP (Shor); 256-bit prime-field ECDLP needs about 2330 logical444 qubits and 1.26e11 Toffoli gates (Roetteler et al. 2017).445 source: roetteler2017quantum446 notes: >447 shor1997polynomial.448449experimental_records:450 - id: E01451 statement: >452 Certicom challenges: ECCp-109 (prime, 109 bits) solved Oct. 15, 2002; ECC2K-108 (Koblitz) Apr. 4,453 2000; ECC2-109 Apr. 8, 2004; the 131-bit challenges and ECC2K-130 remain open in the 2009 document.454 source: certicom2009challenge455 notes: >456 Attack plan for ECC2K-130 in bailey2009breaking (completion not verified).457 - id: E02458 statement: >459 Largest completed prime-field ECDLP: secp112r1 (112-bit), Pollard rho on about 215 PlayStation 3460 consoles at EPFL, 2009 (published 2012).461 source: bos2012solving462 notes: >463 bernstein2011correct later roughly doubled the per-console throughput with a correct negation map.464 - id: E03465 statement: >466 Binary-field records: 113-bit Koblitz curve on an 18-core Virtex-6 FPGA cluster (extrapolated467 24 days, 2014); sect113r1 on 10 Kintex-7 FPGAs at 900 M iterations/s over several months (2015);468 sect113r2 on FPGAs in 2016, 'a prime order very slightly larger than the previous record holder'.469 source: wenger2016harder470 notes: >471 wenger2014solving, bernstein2016faster. No '117.35-bit' record could be verified (unverified.md).472 - id: E04473 statement: >474 SHA-256 collisions: 21 steps (2008), 23/24 steps practical (2008), 27 steps practical (2011),475 28 steps practical and 31 steps at 2^65.5 (2013), 31 steps practical (2024), 37 steps theoretical476 (2026).477 source: li2024first478 notes: >479 nikolic2008collisions, indesteege2008collisions, sanadhya2008new, mendel2011finding, mendel2013improving, zhang2026collision.480 - id: E05481 statement: >482 SHA-256 semi-free-start collisions: 23 steps (2008), 32 steps (2011), 38 steps (2013),483 39 steps practical (2024); free-start collision on 40-step SHA-224 practical (2024);484 SHA-512: 27-step practical collision (2015), 28-step practical and 31-step theoretical (2024),485 38-step SFS at 2^40.5 (2014).486 source: li2024new487 notes: >488 eichlseder2014branching, dobraunig2015analysis.489 - id: E06490 statement: >491 SHA-256 preimages: 43 steps at 2^254.9 (2009); 45 steps (hash) and 52 steps (compression492 function) with bicliques (2012); SHA-512: 46 steps at 2^511.5 (2009), 50/57 steps (2012).493 source: aoki2009preimages494 notes: >495 khovratovich2012bicliques.496 - id: E07497 statement: >498 SHA-1 (contrast): identical-prefix collision at about 2^63.1 (SHAttered, 2017) and chosen-prefix499 collision at about 2^63.4 (2020), both practical; SHA-0 differential collisions (1998) and the500 first theoretical full-SHA-1 collision (2005) preceded them.501 source: stevens2017first502 notes: >503 leurent2020sha1, chabaud1998differential, wang2005finding. The SHA-2 step function (two-input Sigma functions, Maj/Ch, 64 steps) has resisted the same techniques beyond 37 steps.504 - id: E08505 statement: >506 Side channels: remote timing recovered OpenSSL ECDSA keys (Brumley-Tuveri 2011); Minerva recovered507 keys from timing leaks in cards and libraries (2020); LadderLeak needs less than one bit of nonce508 leakage (2020).509 source: brumley2011remote510 notes: >511 jancar2020minerva, aldaya2020ladderleak. Out of scope for attacks, in scope for the constant-time benchmark requirement.512 - id: E09513 statement: >514 Automated discovery baselines: AlphaTensor found a 47-multiplication 4x4 matrix product over F_2515 (2022); FunSearch found new cap-set constructions (2024); AI-guided intuition produced theorems516 in knot theory and representation theory (2021); AlphaGeometry solved 25/30 IMO geometry problems517 (2024); AlphaEvolve improved several algorithmic constructions (2025).518 source: romeraparedes2024mathematical519 notes: >520 fawzi2022discovering, davies2021advancing, trinh2024solving, novikov2025alphaevolve, lu2024ai. None addresses cryptanalysis of standardised primitives; Axis D baseline comparison.521 - id: E10522 statement: >523 Verified bit-blasting: Lean 4 bv_decide proves QF_BV goals by CaDiCaL + LRAT checking inside the524 kernel and beats the previous verified baseline (CoqQFBV) on SMT-LIB.525 source: boving2025interactive526 notes: >527 demoura2021lean. Candidate tool for machine-checking reduced-round SHA-256 identities (Stage 5).528529open_problems:530 - id: O01531 statement: >532 Is the special structure of secp256k1 (p = 2^256 - 2^32 - 977, j = 0, CM discriminant -3,533 efficiently computable order-6 automorphism) exploitable beyond the sqrt(6) rho speedup and the534 GLV constant factor? No attack is known.535 source: galbraith2016recent536 notes: >537 bernstein2014safecurves lists the curve as failing only 'rigidity' and 'ladder'-type criteria, not any attack criterion. Axis A questions A1-A5.538 - id: O02539 statement: >540 Is there any sub-exponential algorithm for the ECDLP over prime fields? Summation-polynomial541 index calculus requires an extension field; no decomposition base with a usable size is known over542 F_p.543 source: galbraith2016recent544 notes: >545 semaev2004summation, gaudry2009index, diem2011discrete, petit2012elliptic.546 - id: O03547 statement: >548 Can generic-group lower bounds be matched by algorithms exploiting the representation in a way549 that is provably impossible for generic algorithms, for prime fields? (Tag tracing does this for550 F_p^* but has no elliptic analogue.)551 source: cheon2012speeding552 notes: >553 Axis A question A3/A4.554 - id: O04555 statement: >556 Practical SHA-256 collision beyond 31 steps and any collision beyond 37 steps; semi-free-start557 beyond 39 steps; preimage beyond 45 (hash) / 52 (compression) steps.558 source: zhang2026collision559 notes: >560 li2024first, li2024new, khovratovich2012bicliques. Axis C questions C1-C5.561 - id: O05562 statement: >563 Tight security of ECDSA without idealising the conversion function, and of Schnorr without the564 random-oracle model.565 source: fersch2016provable566 notes: >567 seurin2012exact, paillier2005discrete. Axis B question B1/B4.568 - id: O06569 statement: >570 Can SAT/SMT solvers, possibly with CAS or learned heuristics, match the hand-tuned571 characteristic-search tools (31-39 steps) rather than stalling at 28 steps?572 source: alamgir2024sha256573 notes: >574 Axis C question C2/C4; Axis D methodology.575 - id: O07576 statement: >577 Can automated hypothesis generation (LLM- or search-based) rediscover known constant-factor578 results (negation map, sqrt(6), GLV) and correctly reject non-results on synthetic groups?579 source: lu2024ai580 notes: >581 novikov2025alphaevolve, romeraparedes2024mathematical. Axis D success criterion.582 - id: O08583 statement: >584 Verification acceleration without changing consensus: how much of BIP340 batch verification and585 ECDSA verification cost can be removed by MSM/endomorphism tricks while preserving bit-exact586 acceptance semantics?587 source: wuille2020bip340588 notes: >589 bernstein2012high, bellare1998fast, wuille2013libsecp256k1. Axis B question B2/B5.590591negative_results:592 - id: N01593 statement: >594 No generic algorithm beats Omega(sqrt(p)) (Shoup/Nechaev); with preprocessing S T^2 =595 Omega~(N) (Corrigan-Gibbs-Kogan). Any proposed generic shortcut is refuted a priori.596 source: shoup1997lower597 notes: >598 corrigangibbs2018discrete.599 - id: N02600 statement: >601 Automorphisms give at most sqrt(|Aut|) on rho: sqrt(2) from negation, sqrt(6) on j = 0 curves;602 careless fruitless-cycle handling can erase the gain (Bos-Kleinjung-Lenstra 2010).603 source: duursma1999speeding604 notes: >605 bos2010negation, bernstein2011correct, wiener1999faster, gallant2000improving. Settles mandate claim 'endomorphism gives at most sqrt(6) on rho' as a known result.606 - id: N03607 statement: >608 MOV/Frey-Rueck does not apply to secp256k1 (huge embedding degree) and the anomalous attack does609 not apply (n != p); SafeCurves verifies both conditions.610 source: bernstein2014safecurves611 notes: >612 menezes1993reducing, frey1994remark, smart1999discrete.613 - id: N04614 statement: >615 Pohlig-Hellman gives nothing on secp256k1 because n is prime and the cofactor is 1.616 source: pohlig1978improved617 notes: >618 certicom2010sec2.619 - id: N05620 statement: >621 Index calculus via summation polynomials fails over prime fields: there is no subfield to define622 a small factor base, the summation-polynomial systems have degree 2^{m-2} per variable, and623 Groebner-basis solving costs more than rho for all parameter choices studied (Gaudry, Diem,624 Petit-Quisquater; survey Galbraith-Gaudry 2016).625 source: galbraith2016recent626 notes: >627 semaev2004summation, gaudry2009index, diem2011discrete, petit2012elliptic.628 - id: N06629 statement: >630 Schnorr cannot be proven equivalent to DL via algebraic reductions without the ROM, and the631 forking-lemma loss q_h is unavoidable for such reductions (Paillier-Vergnaud 2005, Seurin 2012).632 source: paillier2005discrete633 notes: >634 seurin2012exact.635 - id: N07636 statement: >637 Pure SAT (no CAS guidance) finds SHA-256 collisions for at most 28 steps; the 2006 and 2017 SAT638 inversions reach about 20-24 steps; SAT alone is far from the 31/37-step frontier.639 source: alamgir2024sha256640 notes: >641 mironov2006applications, nejati2017adaptive.642 - id: N08643 statement: >644 Chabaud-Joux / Dobbertin-style attacks on SHA-0/SHA-1 do not transfer to SHA-256; only the645 XOR-linearised, symmetric-constant variant is weak (Gilbert-Handschuh 2003).646 source: gilbert2003security647 notes: >648 chabaud1998differential. Reduced-step results since 2008 use different, local-collision-based techniques.649 - id: N09650 statement: >651 Practical ECDLP records stop at 112-113 bits (prime and binary fields); secp256k1 is about 2^71652 times harder than the largest completed prime-field computation.653 source: bos2012solving654 notes: >655 bernstein2016faster, certicom2009challenge. Any experimental claim must be scaled honestly (mandate section 4).656 - id: N10657 statement: >658 ECDSA malleability (s, n - s) and the absence of batch verification are structural features, not659 bugs; BIP340 removes both by design but still needs the ROM.660 source: wuille2020bip340661 notes: >662 fersch2016provable, seurin2012exact.663