1# WP34 — Preliminary research-gap report (Stage 1, literature extraction)23Date: 2026-11-01. Companion files: `db.yaml` (structured database, 21 theorems + 17 algorithms + 64assumptions + 10 bounds + 10 records + 8 open problems + 10 negative results = 82 items),5`records.md` (computational records), `unverified.md` (items left out), `paper/references.bib`6(129 verified entries). All citation keys below exist in `references.bib`.78## 1. What is known (settled by the literature)910**ECDLP, generic setting.** The square-root barrier is a theorem, not a heuristic: any generic11algorithm needs Ω(√p) group operations in a prime-order group (`shoup1997lower`, `nechaev1994complexity`),12and with S bits of curve-specific precomputation the online cost obeys S·T² = Ω̃(N)13(`corrigangibbs2018discrete`), which rho with distinguished points matches (`bernstein2013nonuniform`).14The expected constant is fixed by random-mapping statistics, √(πn/2) (`flajolet1990random`,15`harris1960probability`); r-adding walks reach it for r ≥ 20 (`teske2001random`); parallel collision16search gives a linear speedup in processors at the price of a 1/θ distinguished-point overhead17(`vanoorschot1999parallel`).1819**Endomorphisms give constant factors only.** For secp256k1 (j = 0, CM discriminant −3) the order-620automorphism group yields an expected rho speedup of exactly √6 ≈ 2.45 (`duursma1999speeding`,21`wiener1999faster`, `gallant2000improving`), and even the √2 of the negation map is lost unless22fruitless cycles are handled correctly (`bos2010negation`, `bernstein2011correct`). On the23constructive side, GLV decomposition halves the doubling chain with provable bounds on the24sub-scalars (`gallant2001faster`, `sica2002analysis`, `galbraith2011endomorphisms`). The mandate's25claim "the endomorphism gives at most √6 on rho" is therefore a known result, to be *reproduced*,26not discovered.2728**Non-generic attacks do not apply to secp256k1.** MOV/Frey–Rück need a small embedding degree29(`menezes1993reducing`, `frey1994remark`); the anomalous attack needs n = p (`semaev1998evaluation`,30`smart1999discrete`, `satoh1998fermat`); Pohlig–Hellman needs a composite order (`pohlig1978improved`).31SafeCurves checks all three for secp256k1 (`bernstein2014safecurves`). Index calculus through summation32polynomials (`semaev2004summation`) works only over extension fields (`gaudry2009index`,33`diem2011discrete`, `petit2012elliptic`); **no sub-exponential algorithm is known for prime-field ECDLP**34(`galbraith2016recent`). Computational practice agrees: the largest completed prime-field ECDLP is35112 bits (`bos2012solving`), binary-field records are 113 bits (`wenger2014solving`, `wenger2016harder`,36`bernstein2016faster`), and the 131-bit Certicom challenges are open (`certicom2009challenge`).3738**Signatures.** Schnorr is EUF-CMA under DL in the ROM through the forking lemma39(`pointcheval2000security`, `bellare2006multi`); the loss factor q_h is unavoidable for algebraic40reductions and the ROM cannot be dropped (`paillier2005discrete`, `seurin2012exact`). ECDSA needs an41extra idealisation of the conversion function x(R) mod n (`brown2005generic`, `vaudenay2003security`,42`fersch2016provable`, `fersch2017one`), extended to additive key derivation and presignatures in the43GGM (`groth2022security`). Nonce bias is fatal (`howgravegraham2001lattice`, `breitner2019biased`,44`aldaya2020ladderleak`, `jancar2020minerva`), which is why RFC 6979 and BIP340 derive nonces45deterministically (`pornin2013rfc6979`, `wuille2020bip340`). Batch verification of Schnorr-type46signatures is a solved problem (`naccache1994can`, `bellare1998fast`, `bernstein2012high`) built on47multi-scalar multiplication (`straus1964addition`, `pippenger1980evaluation`, `moller2001algorithms`).4849**SHA-256.** The Merkle–Damgård reduction (`merkle1989one`, `damgard1989design`) and the 200350analysis (`gilbert2003security`) remain the only structural statements about the full function.51Reduced-step cryptanalysis has a clear frontier (see `records.md`): practical collisions for 31 of 6452steps (`li2024first`), theoretical collisions for 37 steps (`zhang2026collision`), practical53semi-free-start collisions for 39 steps (`li2024new`), preimages for 43/45 steps and 52 steps of the54compression function at complexities within a factor 2-4 of brute force (`aoki2009preimages`,55`khovratovich2012bicliques`). Pure SAT stalls at 28 steps; SAT+CAS reproduces the 38-step SFS result56(`mironov2006applications`, `nejati2017adaptive`, `alamgir2024sha256`).5758## 2. What is unexplored or under-explored59601. **Representation-aware generic algorithms over prime fields.** Tag tracing (`cheon2012speeding`)61 shows that the generic lower bound can be matched by algorithms that exploit the *representation*62 of F_p^* elements to make each rho step much cheaper. No elliptic-curve analogue is published. The63 question of whether the x-only / Jacobian representation of secp256k1 admits a cheaper iteration64 function (fewer field multiplications per step, not fewer steps) is open and is testable at scale.652. **Joint use of the order-6 orbit and distinguished points.** The √6 gain is analysed asymptotically;66 the interaction between orbit canonicalisation cost, fruitless 6-cycles and the distinguished-point67 overhead 1/θ has not, to our knowledge, been measured systematically across group sizes with68 confidence intervals. This is a reproducibility target (expected outcome: *known result reproduced*).693. **Preprocessing trade-offs on a fixed curve.** The S·T² curve of `corrigangibbs2018discrete` has70 been matched in theory (`bernstein2013nonuniform`, `lee2011generic`) but concrete, seed-controlled71 measurements on synthetic prime-order curves at 30-60 bits with varying S are rare; they would72 calibrate what "free precomputation" means for a single standardised curve.734. **Sub-exponential ECDLP over F_p.** Nothing in the literature even suggests a factor base. Any74 hypothesis here must be framed as a negative-control experiment (summation-polynomial decomposition75 over small prime fields with explicit Gröbner cost), with the expected classification *rejected*.765. **Verification-side algebra (Axis B).** Fast BIP340 batch verification is implemented in77 `wuille2013libsecp256k1`; what is unexplored is a rigorous, bit-exact catalogue of which algebraic78 rearrangements of sG = R + eP (GLV on both terms, shared-doubling interleaving, random-linear-combination79 batching, x-only recovery of R) are *new identities* versus reformulations, with operation counts.80 `groth2022security` is also the first place to look before claiming anything about derived keys.816. **SHA-256 reduced-step regularities with automated search (Axis C).** The frontier tools are82 hand-tuned characteristic searchers (`mendel2011finding`, `mendel2013improving`, `eichlseder2014branching`)83 and recent SAT/MILP models (`li2024new`, `zhang2026collision`). Open: can solver-based search84 (CaDiCaL 2.0, Kissat, Z3 — `biere2024cadical`, `biere2020cadical`, `demoura2008z3`) reproduce85 the 24- and 27-step practical collisions from scratch, and how do solver conflicts scale in the86 number of steps? The published negative result (28 steps for pure SAT, `alamgir2024sha256`) is the87 baseline to beat or confirm.887. **Formal verification of reduced-round identities.** `boving2025interactive` makes QF_BV facts89 about SHA-256 step functions machine-checkable in Lean 4 (`demoura2021lean`); no published work90 uses it for cryptanalytic bookkeeping (e.g. proving that a differential characteristic is91 contradiction-free for k steps).928. **Automated discovery baselines.** AlphaTensor, FunSearch, AlphaGeometry, AlphaEvolve and the93 AI Scientist (`fawzi2022discovering`, `romeraparedes2024mathematical`, `trinh2024solving`,94 `novikov2025alphaevolve`, `lu2024ai`, `davies2021advancing`) show program search can produce95 verified constructions; none targets standardised cryptographic primitives, so Axis D has no96 published baseline and must define one (e.g. rediscovery rate of the √2 / √6 / GLV results on97 synthetic groups).9899## 3. Mandate claims already settled100101| Mandate claim / question | Status | Sources |102|---|---|---|103| Generic baseline T(n) = O(√n) | theorem (upper and lower bound) | `shanks1971class`, `pollard1978monte`, `shoup1997lower` |104| Endomorphism gives "meaningful improvements beyond constant factors" (A1) | **No**: at most √6 on rho, ≈2× on scalar multiplication | `duursma1999speeding`, `gallant2001faster` |105| Equivalence classes / orbits reduce redundant computation (A2) | Yes, by exactly √|Aut| with fruitless-cycle cost | `wiener1999faster`, `bernstein2011correct` |106| Candidate algorithms provably cannot beat lower bounds (A5) | True for generic algorithms, with and without preprocessing | `shoup1997lower`, `corrigangibbs2018discrete` |107| secp256k1's special form makes it insecure | No known attack; all standard exclusion criteria pass | `bernstein2014safecurves`, `galbraith2016recent` |108| Sub-exponential prime-field ECDLP | none known | `galbraith2016recent` |109| ECDSA vs Schnorr proof structure (B1) | Schnorr: DL + ROM + forking; ECDSA: additionally idealised conversion / GGM | `pointcheval2000security`, `fersch2016provable`, `brown2005generic` |110| Batch verification without consensus change (B2) | known for Schnorr/BIP340, not for ECDSA | `bellare1998fast`, `bernstein2012high`, `wuille2020bip340` |111| Reduced-round SHA-256 regularities (C1) | exploited up to 31 (practical) / 37 (theoretical) steps | `li2024first`, `zhang2026collision` |112| SAT/SMT for reduced-round SHA-256 (C2, C4) | pure SAT ≤ 28 steps; SAT+CAS 38-step SFS | `alamgir2024sha256` |113| Generic hash benchmarks 2^256 / 2^128 | standard; no full-round attack | `nist2015fips180`, `gilbert2003security` |114115## 4. Candidate directions worth testing computationally (for Stage 2)116117- **D1 (Axis A, reproduction):** measure rho / negation / order-6 constants on synthetic j = 0 curves at118 24-56 bits, ≥ 10 seeds each, fit T = a·n^α(log n)^β and confirm α = 1/2 and the √2, √6 ratios with119 bootstrap CIs. Expected classification: *known result reproduced*.120- **D2 (Axis A, exploratory):** cost per rho iteration under alternative representations (affine with121 Montgomery's simultaneous inversion, x-only with orbit canonicalisation, Jacobian) — a representation122 result in the spirit of `cheon2012speeding`; success criterion is field multiplications per step.123- **D3 (Axis A, negative control):** summation-polynomial decomposition over small F_p with explicit124 Gröbner-basis cost versus rho; expected *rejected*.125- **D4 (Axis A, preprocessing):** S·T² measurements on a fixed synthetic curve with S from 2^8 to 2^20.126- **D5 (Axis B):** operation-count benchmark of BIP340 single vs batch verification (N = 1…1024) and127 ECDSA verification with/without GLV, against `wuille2013libsecp256k1`; identity catalogue checked by128 exact arithmetic and, where possible, by Lean (`boving2025interactive`).129- **D6 (Axis C):** SAT encodings of k-step SHA-256 collision and preimage instances for k = 16…28 with130 CaDiCaL/Kissat/Z3, conflict counts and wall-clock, with a random-function control; compare with the131 published 24/27/28-step practical results.132- **D7 (Axis C):** differential-probability measurements of published local collisions as the step count133 grows (mandate C3), using the characteristics of `mendel2013improving` as the reference.134- **D8 (Axis D):** an automated hypothesis loop whose scoring is the classification vocabulary of135 `CLAUDE.md`, evaluated by its ability to rediscover D1 results and reject D3; baseline = random136 hypothesis sampling.137138None of these directions assumes that a shortcut exists; D1, D3 and D6 are explicitly expected to139return known or negative results, which the mandate counts as valid outcomes (Outcome D).140