# WP34 — Preliminary research-gap report (Stage 1, literature extraction)

Date: 2026-11-01. Companion files: db.yaml (structured database, 21 theorems + 17 algorithms + 6 assumptions + 10 bounds + 10 records + 8 open problems + 10 negative results = 82 items), records.md (computational records), unverified.md (items left out), paper/references.bib (129 verified entries). All citation keys below exist in references.bib.

# 1. What is known (settled by the literature)

ECDLP, generic setting. The square-root barrier is a theorem, not a heuristic: any generic algorithm needs Ω(√p) group operations in a prime-order group (shoup1997lower, nechaev1994complexity), and with S bits of curve-specific precomputation the online cost obeys S·T² = Ω̃(N) (corrigangibbs2018discrete), which rho with distinguished points matches (bernstein2013nonuniform). The expected constant is fixed by random-mapping statistics, √(πn/2) (flajolet1990random, harris1960probability); r-adding walks reach it for r ≥ 20 (teske2001random); parallel collision search gives a linear speedup in processors at the price of a 1/θ distinguished-point overhead (vanoorschot1999parallel).

Endomorphisms give constant factors only. For secp256k1 (j = 0, CM discriminant −3) the order-6 automorphism group yields an expected rho speedup of exactly √6 ≈ 2.45 (duursma1999speeding, wiener1999faster, gallant2000improving), and even the √2 of the negation map is lost unless fruitless cycles are handled correctly (bos2010negation, bernstein2011correct). On the constructive side, GLV decomposition halves the doubling chain with provable bounds on the sub-scalars (gallant2001faster, sica2002analysis, galbraith2011endomorphisms). The mandate's claim "the endomorphism gives at most √6 on rho" is therefore a known result, to be reproduced, not discovered.

Non-generic attacks do not apply to secp256k1. MOV/Frey–Rück need a small embedding degree (menezes1993reducing, frey1994remark); the anomalous attack needs n = p (semaev1998evaluation, smart1999discrete, satoh1998fermat); Pohlig–Hellman needs a composite order (pohlig1978improved). SafeCurves checks all three for secp256k1 (bernstein2014safecurves). Index calculus through summation polynomials (semaev2004summation) works only over extension fields (gaudry2009index, diem2011discrete, petit2012elliptic); no sub-exponential algorithm is known for prime-field ECDLP (galbraith2016recent). Computational practice agrees: the largest completed prime-field ECDLP is 112 bits (bos2012solving), binary-field records are 113 bits (wenger2014solving, wenger2016harder, bernstein2016faster), and the 131-bit Certicom challenges are open (certicom2009challenge).

Signatures. Schnorr is EUF-CMA under DL in the ROM through the forking lemma (pointcheval2000security, bellare2006multi); the loss factor q_h is unavoidable for algebraic reductions and the ROM cannot be dropped (paillier2005discrete, seurin2012exact). ECDSA needs an extra idealisation of the conversion function x(R) mod n (brown2005generic, vaudenay2003security, fersch2016provable, fersch2017one), extended to additive key derivation and presignatures in the GGM (groth2022security). Nonce bias is fatal (howgravegraham2001lattice, breitner2019biased, aldaya2020ladderleak, jancar2020minerva), which is why RFC 6979 and BIP340 derive nonces deterministically (pornin2013rfc6979, wuille2020bip340). Batch verification of Schnorr-type signatures is a solved problem (naccache1994can, bellare1998fast, bernstein2012high) built on multi-scalar multiplication (straus1964addition, pippenger1980evaluation, moller2001algorithms).

SHA-256. The Merkle–Damgård reduction (merkle1989one, damgard1989design) and the 2003 analysis (gilbert2003security) remain the only structural statements about the full function. Reduced-step cryptanalysis has a clear frontier (see records.md): practical collisions for 31 of 64 steps (li2024first), theoretical collisions for 37 steps (zhang2026collision), practical semi-free-start collisions for 39 steps (li2024new), preimages for 43/45 steps and 52 steps of the compression function at complexities within a factor 2-4 of brute force (aoki2009preimages, khovratovich2012bicliques). Pure SAT stalls at 28 steps; SAT+CAS reproduces the 38-step SFS result (mironov2006applications, nejati2017adaptive, alamgir2024sha256).

# 2. What is unexplored or under-explored

1. Representation-aware generic algorithms over prime fields. Tag tracing (cheon2012speeding) shows that the generic lower bound can be matched by algorithms that exploit the representation of F_p^* elements to make each rho step much cheaper. No elliptic-curve analogue is published. The question of whether the x-only / Jacobian representation of secp256k1 admits a cheaper iteration function (fewer field multiplications per step, not fewer steps) is open and is testable at scale.
2. Joint use of the order-6 orbit and distinguished points. The √6 gain is analysed asymptotically; the interaction between orbit canonicalisation cost, fruitless 6-cycles and the distinguished-point overhead 1/θ has not, to our knowledge, been measured systematically across group sizes with confidence intervals. This is a reproducibility target (expected outcome: known result reproduced).
3. Preprocessing trade-offs on a fixed curve. The S·T² curve of corrigangibbs2018discrete has been matched in theory (bernstein2013nonuniform, lee2011generic) but concrete, seed-controlled measurements on synthetic prime-order curves at 30-60 bits with varying S are rare; they would calibrate what "free precomputation" means for a single standardised curve.
4. Sub-exponential ECDLP over F_p. Nothing in the literature even suggests a factor base. Any hypothesis here must be framed as a negative-control experiment (summation-polynomial decomposition over small prime fields with explicit Gröbner cost), with the expected classification rejected.
5. Verification-side algebra (Axis B). Fast BIP340 batch verification is implemented in wuille2013libsecp256k1; what is unexplored is a rigorous, bit-exact catalogue of which algebraic rearrangements of sG = R + eP (GLV on both terms, shared-doubling interleaving, random-linear-combination batching, x-only recovery of R) are new identities versus reformulations, with operation counts. groth2022security is also the first place to look before claiming anything about derived keys.
6. SHA-256 reduced-step regularities with automated search (Axis C). The frontier tools are hand-tuned characteristic searchers (mendel2011finding, mendel2013improving, eichlseder2014branching) and recent SAT/MILP models (li2024new, zhang2026collision). Open: can solver-based search (CaDiCaL 2.0, Kissat, Z3 — biere2024cadical, biere2020cadical, demoura2008z3) reproduce the 24- and 27-step practical collisions from scratch, and how do solver conflicts scale in the number of steps? The published negative result (28 steps for pure SAT, alamgir2024sha256) is the baseline to beat or confirm.
7. Formal verification of reduced-round identities. boving2025interactive makes QF_BV facts about SHA-256 step functions machine-checkable in Lean 4 (demoura2021lean); no published work uses it for cryptanalytic bookkeeping (e.g. proving that a differential characteristic is contradiction-free for k steps).
8. Automated discovery baselines. AlphaTensor, FunSearch, AlphaGeometry, AlphaEvolve and the AI Scientist (fawzi2022discovering, romeraparedes2024mathematical, trinh2024solving, novikov2025alphaevolve, lu2024ai, davies2021advancing) show program search can produce verified constructions; none targets standardised cryptographic primitives, so Axis D has no published baseline and must define one (e.g. rediscovery rate of the √2 / √6 / GLV results on synthetic groups).

# 3. Mandate claims already settled

# 4. Candidate directions worth testing computationally (for Stage 2)

• D1 (Axis A, reproduction): measure rho / negation / order-6 constants on synthetic j = 0 curves at 24-56 bits, ≥ 10 seeds each, fit T = a·n^α(log n)^β and confirm α = 1/2 and the √2, √6 ratios with bootstrap CIs. Expected classification: known result reproduced.
• D2 (Axis A, exploratory): cost per rho iteration under alternative representations (affine with Montgomery's simultaneous inversion, x-only with orbit canonicalisation, Jacobian) — a representation result in the spirit of cheon2012speeding; success criterion is field multiplications per step.
• D3 (Axis A, negative control): summation-polynomial decomposition over small F_p with explicit Gröbner-basis cost versus rho; expected rejected.
• D4 (Axis A, preprocessing): S·T² measurements on a fixed synthetic curve with S from 2^8 to 2^20.
• D5 (Axis B): operation-count benchmark of BIP340 single vs batch verification (N = 1…1024) and ECDSA verification with/without GLV, against wuille2013libsecp256k1; identity catalogue checked by exact arithmetic and, where possible, by Lean (boving2025interactive).
• D6 (Axis C): SAT encodings of k-step SHA-256 collision and preimage instances for k = 16…28 with CaDiCaL/Kissat/Z3, conflict counts and wall-clock, with a random-function control; compare with the published 24/27/28-step practical results.
• D7 (Axis C): differential-probability measurements of published local collisions as the step count grows (mandate C3), using the characteristics of mendel2013improving as the reference.
• D8 (Axis D): an automated hypothesis loop whose scoring is the classification vocabulary of CLAUDE.md, evaluated by its ability to rediscover D1 results and reject D3; baseline = random hypothesis sampling.

None of these directions assumes that a shortcut exists; D1, D3 and D6 are explicitly expected to return known or negative results, which the mandate counts as valid outcomes (Outcome D).