# WP34 — Stage 1 structured literature database # Every `source` is a key in paper/references.bib (all verified 2026-11-01 via Crossref / IACR ePrint / # arXiv / DOI / official standard URL). Formulas are plain text. `notes` records caveats and how the # item will be used by the discovery pipeline. theorems: - id: T01 statement: > Hasse bound. For an elliptic curve E over F_q, |#E(F_q) - (q + 1)| <= 2*sqrt(q); equivalently the Frobenius trace t satisfies |t| <= 2 sqrt(q). source: hasse1936theorie notes: > 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). - id: T02 statement: > Group structure. E(F_q) is isomorphic to Z/n1 x Z/n2 with n2 | n1 and n2 | (q - 1); in particular E(F_q) is cyclic or a product of two cyclic groups. source: washington2008elliptic notes: > Also silverman2009arithmetic III.6 / V.1. Pohlig-Hellman (A08) applies to the subgroup structure. - id: T03 statement: > Deuring / CM theory. End(E) over the algebraic closure is Z, an order in an imaginary quadratic field (ordinary case) or an order in a quaternion algebra (supersingular). For secp256k1 (j = 0, p = 1 mod 3) End(E) contains Z[omega], omega a primitive cube root of unity, giving the order-6 automorphism group and the endomorphism phi(x, y) = (beta x, y) with beta^3 = 1 in F_p. source: deuring1941typen notes: > Operational consequences in gallant2001faster and wiener1999faster. CM discriminant -3. - id: T04 statement: > Schoof's algorithm counts #E(F_q) deterministically in O(log^8 q) bit operations by computing the Frobenius trace modulo small primes l and recombining by CRT; SEA improvements (Elkies, Atkin) lower this to O~(log^4 q) heuristically. source: schoof1985elliptic notes: > SEA described in schoof1995counting. Used to validate synthetic-curve orders in the experiments. - id: T05 statement: > Generic lower bound (Shoup 1997, Nechaev 1994). Any generic algorithm that computes discrete logarithms in a cyclic group of prime order p with probability >= 1/2 performs Omega(sqrt(p)) group operations; the same bound holds for the Diffie-Hellman problems. source: shoup1997lower notes: > 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). - id: T06 statement: > Random-mapping statistics (Flajolet-Odlyzko 1990, Harris 1960). For a random mapping on an n-element set, the expected rho length (tail + cycle) of a random starting point is sqrt(pi n / 2) (1 + o(1)); expected tail length and cycle length are each sqrt(pi n / 8). source: flajolet1990random notes: > harris1960probability gives the earlier distributional results. Baseline for all rho experiments; a true random mapping is the negative control (CONVENTIONS 5). - id: T07 statement: > Preprocessing lower bound (Corrigan-Gibbs-Kogan 2018). Any generic discrete-log algorithm with an S-bit advice string, online time T and success probability eps in a group of prime order N satisfies S T^2 = Omega~(eps N); the bound is tight up to logarithmic factors. source: corrigangibbs2018discrete notes: > 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. - id: T08 statement: > Pohlig-Hellman. If the group order factors as prod p_i^{e_i}, a discrete logarithm reduces to sum_i e_i instances in groups of prime order p_i plus CRT; the cost is dominated by the largest prime factor: O(sum_i e_i (log n + sqrt(p_i))) group operations with rho or BSGS. source: pohlig1978improved notes: > secp256k1 has prime order n, so Pohlig-Hellman gives nothing; it matters for synthetic composite-order instances. - id: T09 statement: > MOV / Frey-Rueck reduction. If n | q^k - 1 for small embedding degree k, the Weil (MOV) or Tate (Frey-Rueck) pairing maps the ECDLP in the order-n subgroup into the DLP in F_{q^k}^*, which has subexponential algorithms. source: menezes1993reducing notes: > Tate-pairing version in frey1994remark. For secp256k1 the embedding degree is astronomically large (checked in SafeCurves, bernstein2014safecurves); the reduction does not apply. - id: T10 statement: > Anomalous-curve attack. If #E(F_p) = p (trace 1), the ECDLP is solvable in polynomial time by lifting to the p-adics / Fermat quotients (Semaev, Smart, Satoh-Araki, independently). source: smart1999discrete notes: > semaev1998evaluation and satoh1998fermat are the other two original sources. secp256k1 has n != p, so the attack does not apply. - id: T11 statement: > Summation polynomials (Semaev 2004). For an elliptic curve E, there exist polynomials f_m in m variables of degree 2^{m-2} in each variable such that f_m(x_1, ..., x_m) = 0 iff there exist points P_i with x(P_i) = x_i and P_1 + ... + P_m = O. source: semaev2004summation notes: > Basis of index-calculus on elliptic curves; see T12 / N05 for why this fails over prime fields. - id: T12 statement: > Index calculus on E(F_{q^n}) (Gaudry 2009, Diem 2011). For fixed n >= 2 and q -> infinity, Weil descent on summation polynomials solves the ECDLP in heuristic time O~(q^{2 - 2/n}); Diem proves subexponential complexity for families with n growing like sqrt(log q). source: gaudry2009index notes: > diem2011discrete gives the rigorous version. Requires an extension field: no analogue is known for prime fields (N05). - id: T13 statement: > Forking lemma. From a forger that succeeds with probability eps against a Schnorr-type signature in the random-oracle model after q_h hash queries, one extracts the discrete logarithm with probability about eps^2 / q_h; hence Schnorr is EUF-CMA secure under the DLP in the ROM, with a loss factor q_h. source: pointcheval2000security notes: > General forking lemma (any algorithm) in bellare2006multi. Tightness discussed in T14. - id: T14 statement: > Seurin 2012. In the ROM, any algebraic reduction from the DLP to Schnorr unforgeability must lose a factor close to q_h; the forking-lemma bound is essentially optimal, and the random-oracle assumption cannot be removed for the standard DL-based proof (building on Paillier-Vergnaud 2005). source: seurin2012exact notes: > 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. - id: T15 statement: > ECDSA in the generic group model (Brown 2005). If the conversion function x(R) mod n is modelled via a generic group and the hash is collision-resistant (plus a 'almost-invertibility' condition on the conversion), ECDSA is existentially unforgeable. source: brown2005generic notes: > Also vaudenay2003security (DSA/ECDSA in the ROM-like 'generic' hash model). The generic group model is strong; it ignores the actual structure of secp256k1. - id: T16 statement: > Fersch-Kiltz-Poettering 2016/2017. Modelling the conversion function f(R) = x(R) mod n as a bijective random oracle (and the hash as a random oracle), ECDSA is EUF-CMA secure under the DLP; without the bijective-RO idealisation one still gets one-per-message unforgeability for ECDSA and its variants under appropriate assumptions. source: fersch2016provable notes: > fersch2017one is the one-per-message result. Neither result covers the malleability (s, n - s) of ECDSA, which is inherent. - id: T17 statement: > Groth-Shoup 2022. ECDSA remains secure in the generic group model when additive key derivation (BIP32-style tweaks pk + tG) and presignatures (R computed before the message) are used, with an explicit degradation bound; the proof is given in the GGM with a concrete hash assumption. source: groth2022security notes: > Relevant to Bitcoin derivation paths and threshold ECDSA; the result is in the GGM only. - id: T18 statement: > Nonce leakage breaks ECDSA. Knowledge of a few bits of the nonce k for many signatures reduces key recovery to a hidden-number / closest-vector problem solvable by lattice reduction (Howgrave-Graham and Smart 2001); real-world biased nonces were exploited in cryptocurrencies (Breitner-Heninger 2019); less than one bit of leakage suffices with enough signatures (LadderLeak 2020). source: howgravegraham2001lattice notes: > breitner2019biased, aldaya2020ladderleak (authors Aranha, Novaes, Takahashi, Tibouchi, Yarom), jancar2020minerva. Motivates deterministic nonces (pornin2013rfc6979, wuille2020bip340). - id: T19 statement: > Merkle-Damgaard. If the compression function f is collision resistant and the padding encodes the message length (MD strengthening), the iterated hash H is collision resistant. source: merkle1989one notes: > damgard1989design is the independent proof. SHA-256 follows this construction (nist2015fips180) with 64-step compression on 512-bit blocks and 256-bit chaining value. - id: T20 statement: > Tseitin transformation. Any Boolean circuit with m gates has an equisatisfiable CNF with O(m) clauses and O(m) auxiliary variables; this is the encoding used to turn reduced-step SHA-256 into SAT instances. source: tseitin1983complexity notes: > Used by mironov2006applications, nejati2017adaptive, alamgir2024sha256 and by Lean's bv_decide (boving2025interactive). - id: T21 statement: > Shor 1997. On a quantum computer the discrete logarithm problem in any cyclic group with efficiently computable group law is solvable in polynomial time; resource estimates for 256-bit prime-field ECDLP are about 2330 logical qubits and 1.26e11 Toffoli gates (Roetteler et al. 2017). source: shor1997polynomial notes: > roetteler2017quantum. Out of scope for the classical experiments; cited in the implications section. algorithms: - id: A01 statement: > Baby-step giant-step (Shanks 1971). Deterministic, O(sqrt(n)) group operations and O(sqrt(n)) memory; with m = ceil(sqrt(n)) baby steps and giant steps of size m. source: shanks1971class notes: > 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. - id: A02 statement: > Pollard rho (1978). Iterate a pseudo-random walk x_{i+1} = f(x_i) on the group with a cycle-finding method; a collision x_i = x_j with distinct (a, b) representations yields the logarithm. Expected cost about sqrt(pi n / 2) group operations with O(1) memory when f behaves like a random mapping. source: pollard1978monte notes: > Cycle finding by Floyd (original) or Brent (brent1980improved, fewer function evaluations). The original 3-partition walk is not random enough (teske1998speeding). - id: A03 statement: > Pollard kangaroo / lambda (1978, 2000). Two walks (tame, wild) with jumps of mean size about sqrt(w)/2 solve a logarithm known to lie in an interval of width w in about 2 sqrt(w) operations; the 2000 paper gives the refined 'monopoly' analysis and the parallel version. source: pollard2000kangaroos notes: > Interval DLP improvements with equivalence classes in galbraith2010interval (about 1.36 sqrt(w)) and the 'grumpy giants' BSGS variant in bernstein2012two. - id: A04 statement: > r-adding walks (Teske 1998/2001). With r >= 20 random multipliers, the adding walk x -> x + M_{h(x)} behaves close to a random mapping and the rho cost approaches sqrt(pi n / 2); r = 3 is about 30% slower; mixed adding/doubling walks also work. source: teske2001random notes: > teske1998speeding is the ANTS version. Partition count r is a free parameter for sensitivity analysis. - id: A05 statement: > Parallel collision search with distinguished points (van Oorschot-Wiener 1999). m processors each run independent walks and report points with a distinguishing property (probability theta) to a central store; expected time sqrt(pi n / 2)/m + 1/theta per processor, i.e. linear speedup with memory about theta sqrt(pi n / 2) points. source: vanoorschot1999parallel notes: > Used by every ECDLP record since 2000 (bos2012solving, wenger2014solving, bernstein2016faster). The additive overhead 1/theta is the price of distinguished points. - id: A06 statement: > Negation map. Iterating on classes {P, -P} halves the effective group size, giving an expected speedup of sqrt(2) for rho; it introduces fruitless 2-cycles (and longer cycles) that must be detected and escaped, costing a constant factor if handled carelessly. source: wiener1999faster notes: > 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. - id: A07 statement: > Automorphism speedup. If E has an efficiently computable automorphism group of order m acting on the order-n subgroup, rho on orbits gives an expected speedup of sqrt(m): sqrt(2 l) for Koblitz curves over F_{2^l} (Frobenius and negation), sqrt(6) for j = 0 curves such as secp256k1 (order-6 group generated by (x, y) -> (beta x, -y)), sqrt(4) for j = 1728. source: duursma1999speeding notes: > 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. - id: A08 statement: > GLV scalar decomposition. For a curve with endomorphism phi acting as [lambda], write k = k1 + k2 lambda (mod n) with |k1|, |k2| about sqrt(n) via a short lattice basis; the scalar multiplication kP = k1 P + k2 phi(P) with simultaneous (Straus-Shamir) double-and-add roughly halves the number of doublings. source: gallant2001faster notes: > 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). - id: A09 statement: > Multi-scalar multiplication. Straus (1964) / Shamir trick computes a1 P1 + ... + ak Pk with one shared doubling chain; Pippenger (1980) achieves about (l / log l)-type savings for many terms via bucket methods; interleaving with sliding windows (Moeller 2001) is the practical choice for k = 2 (ECDSA/Schnorr verification). source: straus1964addition notes: > pippenger1980evaluation, moller2001algorithms. Batch verification reduces to one large MSM (A11). - id: A10 statement: > Coordinates and ladders. Mixed Jacobian/affine coordinates minimise field operations for double-and-add (Cohen-Miyaji-Ono 1998); Montgomery's x-only ladder (1987) and its Weierstrass adaptation (Brier-Joye 2002) give uniform, side-channel-resistant scalar multiplication. source: cohen1998efficient notes: > montgomery1987speeding, brier2002weierstrass. Generalised-Mersenne reduction for p = 2^256 - 2^32 - 977 follows solinas1999generalized. Timing attacks: kocher1996timing, brumley2011remote. - id: A11 statement: > Batch verification. For Schnorr-type signatures, verifying N signatures reduces to one random linear combination sum a_i (s_i G - R_i - e_i P_i) = O with random 128-bit a_i, soundness error 2^-128 (Naccache et al. 1994; Bellare-Garay-Rabin 1998); with Pippenger's MSM the cost per signature drops to a fraction of a single verification (Ed25519: roughly half, Bernstein et al. 2012). source: bellare1998fast notes: > naccache1994can, bernstein2012high. BIP340 (wuille2020bip340) is designed for batch verification; ECDSA is not batch-verifiable without recovering R (B04). - id: A12 statement: > Schoof / SEA point counting (see T04) and Hasse-interval search are used to generate synthetic prime-order curves at 20-80 bits for the experiments. source: schoof1995counting notes: > Implementation gate: cross-check orders with two independent implementations (CONVENTIONS). - id: A13 statement: > Tag tracing (Cheon-Hong-Kim 2012). In prime-field (multiplicative) groups, the rho walk can be advanced without full group multiplications by tracing a tag of the product, giving large constant-factor speedups; the technique is specific to F_p^* representation. source: cheon2012speeding notes: > No analogue for elliptic-curve groups is known (relevant to A4 of the mandate: representation-specific speedups). - id: A14 statement: > Automated differential-characteristic search for SHA-2 (Mendel-Nad-Schlaeffer 2011/2013): guess-and-determine over generalised conditions with contradiction detection; the 2013 extension to longer local collisions produced 28-step practical, 31-step theoretical and 38-step semi-free-start collisions. source: mendel2011finding notes: > mendel2013improving; branching heuristics in eichlseder2014branching. SAT/MILP-based successors in li2024new, li2024first, zhang2026collision. - id: A15 statement: > SAT-based cryptanalysis of hash functions (Mironov-Zhang 2006). Encode the step function with Tseitin and solve with CDCL; MapleCrypt adds adaptive restarts and CEGAR for inversion (Nejati et al. 2017); programmatic SAT with a CAS reproduces the 38-step SFS collision and finds pure-SAT collisions only up to 28 steps (Alamgir-Nejati-Bright 2024). source: mironov2006applications notes: > nejati2017adaptive, alamgir2024sha256. Solvers: biere2020cadical (Kissat), biere2024cadical (CaDiCaL 2.0), demoura2008z3 (SMT). Lean 4 bv_decide (boving2025interactive) checks LRAT proofs from CaDiCaL inside the kernel. - id: A16 statement: > Biclique meet-in-the-middle preimages (Khovratovich-Rechberger-Savelieva 2012) extend the MITM preimage attacks of Aoki et al. 2009 from 43 to 45 steps of SHA-256 (hash) and 52 steps (compression function), all with complexity close to 2^256. source: khovratovich2012bicliques notes: > aoki2009preimages. These are not practical; they are the step-count frontier for preimages. - id: A17 statement: > Deterministic nonces: RFC 6979 derives k = HMAC_DRBG(d, H(m)); BIP340 derives the nonce from a tagged hash of (auxiliary randomness xor d), P, m and uses x-only keys with even-y normalisation and challenge e = H_tag(r || P || m). source: pornin2013rfc6979 notes: > wuille2020bip340; Taproot usage in wuille2020bip341. Both remove the nonce-reuse failure mode (T18) but not side channels. security_assumptions: - id: S01 statement: > ECDLP on secp256k1: given G and Q = dG in the prime-order-n subgroup (n about 2^256), computing d requires about 2^128 group operations with the best known (generic) algorithms; the sqrt(6) automorphism gain lowers this to about 2^126.7 but no non-generic attack is known. source: galbraith2016recent notes: > Parameters from certicom2010sec2; curve analysis in bernstein2014safecurves. Baseline assumption for Axis A. - id: S02 statement: > Random-oracle assumption on SHA-256 for Schnorr/BIP340 proofs; the challenge hash must be modelled as a random oracle, and Seurin shows this cannot be avoided for the DL-based reduction. source: seurin2012exact notes: > Links Axis B to Axis C: any structural regularity in SHA-256 would weaken the ROM idealisation before it weakens the DLP. - id: S03 statement: > ECDSA security relies additionally on idealising the conversion function x(R) mod n (bijective random oracle or generic group); ECDSA is inherently malleable (s <-> n - s), which is why Bitcoin enforces low-s and why BIP340 Schnorr is preferred for new outputs. source: fersch2016provable notes: > brown2005generic, groth2022security. Malleability is a property, not a break. - id: S04 statement: > Collision resistance of SHA-256 at the 2^128 level and preimage resistance at 2^256 (ideal-hash benchmarks); the Merkle-Damgaard structure makes these reduce to the compression function. source: nist2015fips180 notes: > merkle1989one. Reduced-step results (E-series) do not threaten the 64-step function (gilbert2003security). - id: S05 statement: > Generic-group model: lower bounds (T05) and ECDSA/presignature proofs (T15, T17) hold only for algorithms that ignore the encoding of group elements; secp256k1's special p and j = 0 are exactly the kind of structure the GGM cannot see. source: shoup1997lower notes: > This is the formal gap that Axis A probes: is there any representation-aware algorithm? See open problems. - id: S06 statement: > Non-uniform / preprocessing security: with a 2^S precomputation table specific to secp256k1, the online ECDLP cost is about sqrt(n / S) (T07); a 2^80 table would give 2^88 online operations. The precomputation itself costs about 2^128 (bernstein2013nonuniform). source: bernstein2013nonuniform notes: > corrigangibbs2018discrete. Shows that 'free precomputation' claims need to account for the one-time cost; relevant to any claimed shortcut that amortises over many keys. complexity_bounds: - id: C01 statement: > Expected rho iterations for a random mapping on n points: sqrt(pi n / 2) about 1.2533 sqrt(n); with the negation map sqrt(pi n / 4) about 0.886 sqrt(n); with the order-6 automorphism sqrt(pi n / 12) about 0.512 sqrt(n). source: flajolet1990random notes: > Second and third figures from wiener1999faster / duursma1999speeding assuming perfect handling of fruitless cycles (bernstein2011correct). - id: C02 statement: > Parallel rho with m processors and distinguishing probability theta: expected time (sqrt(pi n / 2)/m + 1/theta) iterations per processor; memory about theta sqrt(pi n / 2) points. source: vanoorschot1999parallel notes: > The experiments must measure the 1/theta overhead and the linear scaling in m. - id: C03 statement: > BSGS: sqrt(n) group operations and sqrt(n) stored points, deterministic; interval of width w: about 2 sqrt(w) for kangaroo (Pollard 2000), about 1.36 sqrt(w) with equivalence classes (Galbraith-Ruprai 2010), and BSGS variants in bernstein2012two. source: shanks1971class notes: > pollard2000kangaroos, galbraith2010interval. - id: C04 statement: > Generic lower bound Omega(sqrt(p)) for prime p (T05); with S bits of preprocessing S T^2 = Omega~(N) (T07). Any claimed generic algorithm beating these is wrong. source: shoup1997lower notes: > corrigangibbs2018discrete. Serves as the falsification test for Axis A hypotheses that are generic. - id: C05 statement: > Index calculus on E(F_{q^n}): O~(q^{2 - 2/n}) for fixed n (Gaudry), subexponential exp(O(log^{2/3} q)) type for suitable families (Diem); summation-polynomial systems over prime fields have no known subexponential solution (Petit-Quisquater analyse the Weil-descent systems and give heuristics for binary fields only). source: gaudry2009index notes: > diem2011discrete, petit2012elliptic, surveyed in galbraith2016recent. - id: C06 statement: > GLV: with |k1|, |k2| < C sqrt(n) (explicit C from Sica-Ciet-Quisquater), the double-scalar computation needs about log2(n)/2 doublings instead of log2(n); the gain is a constant factor near 1.5-2 in practice. source: sica2002analysis notes: > gallant2001faster. - id: C07 statement: > Batch verification of N Schnorr signatures: about one MSM of size 2N + 1 with 128-bit coefficients; with Pippenger the amortised cost per signature is roughly 1/2 to 1/3 of a single verification for N in the hundreds (Ed25519 measurements: about 134k cycles per signature in a batch of 64 versus 2.3x more individually, Bernstein et al. 2012). source: bernstein2012high notes: > bellare1998fast, pippenger1980evaluation. Axis B benchmark target. - id: C08 statement: > SHA-256 collision frontier: practical 31 steps (1.2 h on 64 threads), theoretical 37 steps, semi-free-start practical 39 steps; preimage frontier 43 steps (2^254.9), 45 steps (biclique, hash), 52 steps (biclique, compression function). source: li2024first notes: > zhang2026collision, li2024new, aoki2009preimages, khovratovich2012bicliques; full table in literature/records.md. - id: C09 statement: > SAT-based SHA-256: pure CDCL finds collisions only up to 28 steps; with CAS guidance a 38-step semi-free-start collision is reproduced (Alamgir et al. 2024). Earlier SAT inversions reach only about 20-24 steps (Mironov-Zhang 2006; Nejati et al. 2017). source: alamgir2024sha256 notes: > These numbers are the baseline for Axis C research question C4 (reproduce known results with automated search). - id: C10 statement: > Quantum: polynomial time for ECDLP (Shor); 256-bit prime-field ECDLP needs about 2330 logical qubits and 1.26e11 Toffoli gates (Roetteler et al. 2017). source: roetteler2017quantum notes: > shor1997polynomial. experimental_records: - id: E01 statement: > Certicom challenges: ECCp-109 (prime, 109 bits) solved Oct. 15, 2002; ECC2K-108 (Koblitz) Apr. 4, 2000; ECC2-109 Apr. 8, 2004; the 131-bit challenges and ECC2K-130 remain open in the 2009 document. source: certicom2009challenge notes: > Attack plan for ECC2K-130 in bailey2009breaking (completion not verified). - id: E02 statement: > Largest completed prime-field ECDLP: secp112r1 (112-bit), Pollard rho on about 215 PlayStation 3 consoles at EPFL, 2009 (published 2012). source: bos2012solving notes: > bernstein2011correct later roughly doubled the per-console throughput with a correct negation map. - id: E03 statement: > Binary-field records: 113-bit Koblitz curve on an 18-core Virtex-6 FPGA cluster (extrapolated 24 days, 2014); sect113r1 on 10 Kintex-7 FPGAs at 900 M iterations/s over several months (2015); sect113r2 on FPGAs in 2016, 'a prime order very slightly larger than the previous record holder'. source: wenger2016harder notes: > wenger2014solving, bernstein2016faster. No '117.35-bit' record could be verified (unverified.md). - id: E04 statement: > SHA-256 collisions: 21 steps (2008), 23/24 steps practical (2008), 27 steps practical (2011), 28 steps practical and 31 steps at 2^65.5 (2013), 31 steps practical (2024), 37 steps theoretical (2026). source: li2024first notes: > nikolic2008collisions, indesteege2008collisions, sanadhya2008new, mendel2011finding, mendel2013improving, zhang2026collision. - id: E05 statement: > SHA-256 semi-free-start collisions: 23 steps (2008), 32 steps (2011), 38 steps (2013), 39 steps practical (2024); free-start collision on 40-step SHA-224 practical (2024); SHA-512: 27-step practical collision (2015), 28-step practical and 31-step theoretical (2024), 38-step SFS at 2^40.5 (2014). source: li2024new notes: > eichlseder2014branching, dobraunig2015analysis. - id: E06 statement: > SHA-256 preimages: 43 steps at 2^254.9 (2009); 45 steps (hash) and 52 steps (compression function) with bicliques (2012); SHA-512: 46 steps at 2^511.5 (2009), 50/57 steps (2012). source: aoki2009preimages notes: > khovratovich2012bicliques. - id: E07 statement: > SHA-1 (contrast): identical-prefix collision at about 2^63.1 (SHAttered, 2017) and chosen-prefix collision at about 2^63.4 (2020), both practical; SHA-0 differential collisions (1998) and the first theoretical full-SHA-1 collision (2005) preceded them. source: stevens2017first notes: > leurent2020sha1, chabaud1998differential, wang2005finding. The SHA-2 step function (two-input Sigma functions, Maj/Ch, 64 steps) has resisted the same techniques beyond 37 steps. - id: E08 statement: > Side channels: remote timing recovered OpenSSL ECDSA keys (Brumley-Tuveri 2011); Minerva recovered keys from timing leaks in cards and libraries (2020); LadderLeak needs less than one bit of nonce leakage (2020). source: brumley2011remote notes: > jancar2020minerva, aldaya2020ladderleak. Out of scope for attacks, in scope for the constant-time benchmark requirement. - id: E09 statement: > Automated discovery baselines: AlphaTensor found a 47-multiplication 4x4 matrix product over F_2 (2022); FunSearch found new cap-set constructions (2024); AI-guided intuition produced theorems in knot theory and representation theory (2021); AlphaGeometry solved 25/30 IMO geometry problems (2024); AlphaEvolve improved several algorithmic constructions (2025). source: romeraparedes2024mathematical notes: > fawzi2022discovering, davies2021advancing, trinh2024solving, novikov2025alphaevolve, lu2024ai. None addresses cryptanalysis of standardised primitives; Axis D baseline comparison. - id: E10 statement: > Verified bit-blasting: Lean 4 bv_decide proves QF_BV goals by CaDiCaL + LRAT checking inside the kernel and beats the previous verified baseline (CoqQFBV) on SMT-LIB. source: boving2025interactive notes: > demoura2021lean. Candidate tool for machine-checking reduced-round SHA-256 identities (Stage 5). open_problems: - id: O01 statement: > Is the special structure of secp256k1 (p = 2^256 - 2^32 - 977, j = 0, CM discriminant -3, efficiently computable order-6 automorphism) exploitable beyond the sqrt(6) rho speedup and the GLV constant factor? No attack is known. source: galbraith2016recent notes: > bernstein2014safecurves lists the curve as failing only 'rigidity' and 'ladder'-type criteria, not any attack criterion. Axis A questions A1-A5. - id: O02 statement: > Is there any sub-exponential algorithm for the ECDLP over prime fields? Summation-polynomial index calculus requires an extension field; no decomposition base with a usable size is known over F_p. source: galbraith2016recent notes: > semaev2004summation, gaudry2009index, diem2011discrete, petit2012elliptic. - id: O03 statement: > Can generic-group lower bounds be matched by algorithms exploiting the representation in a way that is provably impossible for generic algorithms, for prime fields? (Tag tracing does this for F_p^* but has no elliptic analogue.) source: cheon2012speeding notes: > Axis A question A3/A4. - id: O04 statement: > Practical SHA-256 collision beyond 31 steps and any collision beyond 37 steps; semi-free-start beyond 39 steps; preimage beyond 45 (hash) / 52 (compression) steps. source: zhang2026collision notes: > li2024first, li2024new, khovratovich2012bicliques. Axis C questions C1-C5. - id: O05 statement: > Tight security of ECDSA without idealising the conversion function, and of Schnorr without the random-oracle model. source: fersch2016provable notes: > seurin2012exact, paillier2005discrete. Axis B question B1/B4. - id: O06 statement: > Can SAT/SMT solvers, possibly with CAS or learned heuristics, match the hand-tuned characteristic-search tools (31-39 steps) rather than stalling at 28 steps? source: alamgir2024sha256 notes: > Axis C question C2/C4; Axis D methodology. - id: O07 statement: > Can automated hypothesis generation (LLM- or search-based) rediscover known constant-factor results (negation map, sqrt(6), GLV) and correctly reject non-results on synthetic groups? source: lu2024ai notes: > novikov2025alphaevolve, romeraparedes2024mathematical. Axis D success criterion. - id: O08 statement: > Verification acceleration without changing consensus: how much of BIP340 batch verification and ECDSA verification cost can be removed by MSM/endomorphism tricks while preserving bit-exact acceptance semantics? source: wuille2020bip340 notes: > bernstein2012high, bellare1998fast, wuille2013libsecp256k1. Axis B question B2/B5. negative_results: - id: N01 statement: > No generic algorithm beats Omega(sqrt(p)) (Shoup/Nechaev); with preprocessing S T^2 = Omega~(N) (Corrigan-Gibbs-Kogan). Any proposed generic shortcut is refuted a priori. source: shoup1997lower notes: > corrigangibbs2018discrete. - id: N02 statement: > Automorphisms give at most sqrt(|Aut|) on rho: sqrt(2) from negation, sqrt(6) on j = 0 curves; careless fruitless-cycle handling can erase the gain (Bos-Kleinjung-Lenstra 2010). source: duursma1999speeding notes: > bos2010negation, bernstein2011correct, wiener1999faster, gallant2000improving. Settles mandate claim 'endomorphism gives at most sqrt(6) on rho' as a known result. - id: N03 statement: > MOV/Frey-Rueck does not apply to secp256k1 (huge embedding degree) and the anomalous attack does not apply (n != p); SafeCurves verifies both conditions. source: bernstein2014safecurves notes: > menezes1993reducing, frey1994remark, smart1999discrete. - id: N04 statement: > Pohlig-Hellman gives nothing on secp256k1 because n is prime and the cofactor is 1. source: pohlig1978improved notes: > certicom2010sec2. - id: N05 statement: > Index calculus via summation polynomials fails over prime fields: there is no subfield to define a small factor base, the summation-polynomial systems have degree 2^{m-2} per variable, and Groebner-basis solving costs more than rho for all parameter choices studied (Gaudry, Diem, Petit-Quisquater; survey Galbraith-Gaudry 2016). source: galbraith2016recent notes: > semaev2004summation, gaudry2009index, diem2011discrete, petit2012elliptic. - id: N06 statement: > Schnorr cannot be proven equivalent to DL via algebraic reductions without the ROM, and the forking-lemma loss q_h is unavoidable for such reductions (Paillier-Vergnaud 2005, Seurin 2012). source: paillier2005discrete notes: > seurin2012exact. - id: N07 statement: > Pure SAT (no CAS guidance) finds SHA-256 collisions for at most 28 steps; the 2006 and 2017 SAT inversions reach about 20-24 steps; SAT alone is far from the 31/37-step frontier. source: alamgir2024sha256 notes: > mironov2006applications, nejati2017adaptive. - id: N08 statement: > Chabaud-Joux / Dobbertin-style attacks on SHA-0/SHA-1 do not transfer to SHA-256; only the XOR-linearised, symmetric-constant variant is weak (Gilbert-Handschuh 2003). source: gilbert2003security notes: > chabaud1998differential. Reduced-step results since 2008 use different, local-collision-based techniques. - id: N09 statement: > Practical ECDLP records stop at 112-113 bits (prime and binary fields); secp256k1 is about 2^71 times harder than the largest completed prime-field computation. source: bos2012solving notes: > bernstein2016faster, certicom2009challenge. Any experimental claim must be scaled honestly (mandate section 4). - id: N10 statement: > ECDSA malleability (s, n - s) and the absence of batch verification are structural features, not bugs; BIP340 removes both by design but still needs the ROM. source: wuille2020bip340 notes: > fersch2016provable, seurin2012exact.