Sharp Oblivious Sequential Time-Memory Curve for Finding a 3-Way Collision

Statement: AI-written, not yet formalized. Proof: open – no attempt yet.

Setting

Throughout, \(N \geq 2\) and \(f\colon [N] \to [N]\) is a uniformly random function, available only through an oracle answering \(x \mapsto f(x)\). A \(k\)-collision is a set of \(k\) distinct points of \([N]\) with a common image under \(f\); a 3-collision is the case \(k = 3\). Asymptotic notation \(\tilde O, \tilde\Omega, \tilde\Theta\) suppresses factors polylogarithmic in \(N\). Success probabilities are over the choice of \(f\) and any coins of the algorithm.

A branching program – the model of Borodin and Cook, specialised to a random-function oracle – queries one point of \([N]\) at a time, with its state between queries capped at \(S\) bits; the state may encode anything, so one cannot say what a program knows. It is oblivious if its query schedule is fixed in advance, independent of the answers seen so far, and repetition-free if no point is queried twice.

Definition (branching program)

A branching program of length \(T\) and width \(W\) is a DAG on levels \(0,\dots,T\) with at most \(W\) nodes per level, in which every node below level \(T\) carries a label \(x \in [N]\) and has one outgoing edge for each \(y \in [N]\), and every node at level \(T\) carries a label in \([N]^3\). It is run by starting at the source, querying the label of the current node, following the edge labelled by the answer, and reading the label of the sink reached; it succeeds if that label is a \(3\)-collision. Its space is \(S = \log_2 W\), counted in bits. It is oblivious if all nodes at a level carry the same label, so that the query schedule \(w_1,\dots,w_T\) is fixed in advance, and repetition-free if no point labels two levels.

Two facts fix the landscape. The query threshold is \(N^{2/3}\): among \(q\) queried points the expected number of \(3\)-collisions is \(\binom{q}{3}N^{-2}\), so \(q = \Theta(N^{2/3})\) queries are necessary and sufficient for constant success probability, for any algorithm at any memory bound (Suzuki, Tonien, Kurosawa and Toyota, ICISC 2006). And the oblivious base case is proved: every repetition-free oblivious branching program succeeding with probability at least \(1/2\) satisfies \(T \cdot (S + \log_2 N) = \tilde\Omega(N)\), via the multi-pass streaming switching lemma of Dinur (EUROCRYPT 2020) applied to the answer stream. This is the only lower bound known at \(k=3\) that mentions memory at all, and it is tight only at \(S\) polylogarithmic; for adaptive programs nothing memory-sensitive is known.

The Conjecture

Conjecture (the oblivious sequential curve at k=3)

Every repetition-free oblivious branching program succeeding with probability at least \(1/2\) satisfies \[ T \;=\; \tilde\Omega\bigl(\max\{\, N^{2/3},\; N/\sqrt{S} \,\}\bigr), \] equivalently \(T \cdot S^{1/2} = \tilde\Omega(N)\) for \(S \le N^{2/3}\).

The first clause carries no content; all of it is in \(T \cdot S^{1/2}\). The bound is tight: an oblivious program can accumulate \(P \le S\) collision pairs at cost \(\tilde\Theta(PN/S)\) and then hunt a third preimage of one of the \(P\) recorded values in \(\tilde\Theta(N/P)\) further queries, both phases non-adaptively; balancing at \(P = \sqrt S\) gives \(T = \tilde\Theta(N/\sqrt S)\). So a factor \(\sqrt S\) separates the proved base case from the conjecture inside its own class, and the two clauses cross at \(S = N^{2/3}\), where the curve meets the query threshold and the problem closes.

At \(k=2\) memory is free: Pollard’s rho method with Brent’s cycle detection finds a \(2\)-collision in \(\Theta(\sqrt N)\) queries using \(O(\log N)\) bits, and that count is optimal even with unbounded memory. Consequently the conjecture is false at \(k=2\), and no proof of it can be indifferent to the collision order.

This conjecture is open – no proof exists yet.

Once (an attempt at) a proof exists, add its own .tex source and compiled PDF (e.g. latex/proof.tex / pdf/proof.pdf) and link them here, following the same convention as the statement.

Formal artifact.

Not yet formalized in Lean.

The question is not whether a time-memory tradeoff exists but whether the oblivious sequential curve is sharp at \(k = 3\). Two facts bracket it: the query threshold is \(\Theta(N^{2/3})\) for any algorithm at any memory bound, so nothing below that is achievable however much space is used; and the Borodin–Cook branching-program model charges only for state between queries, so a lower bound in it says nothing about what a program knows, only about what it can carry.

Obliviousness is the hypothesis doing the work. A fixed query schedule is what makes the counting tractable, and it is also what a solver should be most suspicious of, since adaptive algorithms are the ones actually used. See the problem page.

Attempt a proof closing the factor-\(\sqrt S\) gap between the proved oblivious base case and the matching table-and-hunt algorithm; the companion note argues this needs no new proof technique in either direction, and calls it the smallest open quantity in the larger family of related conjectures.
Formalize the statement in Lean; not yet attempted.