# 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

| Mandate claim / question | Status | Sources |
|---|---|---|
| Generic baseline T(n) = O(√n) | theorem (upper and lower bound) | `shanks1971class`, `pollard1978monte`, `shoup1997lower` |
| Endomorphism gives "meaningful improvements beyond constant factors" (A1) | **No**: at most √6 on rho, ≈2× on scalar multiplication | `duursma1999speeding`, `gallant2001faster` |
| Equivalence classes / orbits reduce redundant computation (A2) | Yes, by exactly √|Aut| with fruitless-cycle cost | `wiener1999faster`, `bernstein2011correct` |
| Candidate algorithms provably cannot beat lower bounds (A5) | True for generic algorithms, with and without preprocessing | `shoup1997lower`, `corrigangibbs2018discrete` |
| secp256k1's special form makes it insecure | No known attack; all standard exclusion criteria pass | `bernstein2014safecurves`, `galbraith2016recent` |
| Sub-exponential prime-field ECDLP | none known | `galbraith2016recent` |
| ECDSA vs Schnorr proof structure (B1) | Schnorr: DL + ROM + forking; ECDSA: additionally idealised conversion / GGM | `pointcheval2000security`, `fersch2016provable`, `brown2005generic` |
| Batch verification without consensus change (B2) | known for Schnorr/BIP340, not for ECDSA | `bellare1998fast`, `bernstein2012high`, `wuille2020bip340` |
| Reduced-round SHA-256 regularities (C1) | exploited up to 31 (practical) / 37 (theoretical) steps | `li2024first`, `zhang2026collision` |
| SAT/SMT for reduced-round SHA-256 (C2, C4) | pure SAT ≤ 28 steps; SAT+CAS 38-step SFS | `alamgir2024sha256` |
| Generic hash benchmarks 2^256 / 2^128 | standard; no full-round attack | `nist2015fips180`, `gilbert2003security` |

## 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).