Finding a \(k\)-way collision with bounded memory
How much does a bound on an algorithm’s working memory slow down finding k inputs of a random function with a common output?
Motivation
A \(k\)-collision is a set of \(k\) distinct inputs of a random function \(f\colon[N]\to[N]\) sharing a common output. Finding one costs \(\Theta(N^{(k-1)/k})\) queries with no bound on memory at all. Real attackers are memory-bounded, and the question is how much a bound on working memory (the state an algorithm carries between queries, as opposed to total running time or offline precomputation) trades against query count. At \(k=2\) memory turns out to be entirely free: Pollard’s rho method finds a \(2\)-collision in the optimal \(\Theta(\sqrt N)\) queries using only \(O(\log N)\) bits. The conjectures gathered under this hub concern the smallest case where this is believed to fail, \(k=3\), in the classical time-space branching-program model of Borodin and Cook (SIAM J. Comput., 1982), specialised to a random-function oracle.
Provenance and history
The query threshold \(N^{2/3}\) for \(3\)-collisions – necessary and sufficient for constant success probability, at any memory bound whatsoever – is a classical result (Suzuki, Tonien, Kurosawa and Toyota, ICISC 2006). Dinur’s multi-pass streaming switching lemma (EUROCRYPT 2020) gives the first memory-sensitive lower bound, but only for oblivious branching programs (those whose query schedule is fixed in advance, independent of the answers seen), and it falls short of the best known algorithm by a factor of \(\sqrt S\) in that same restricted class. The statement recorded here (by Pooya Farshim; see the linked PDF) closes exactly that gap for the sequential oblivious case. It is one piece of a much larger family of related conjectures – covering parallel programs, fully adaptive (non-oblivious) programs, and finding many disjoint \(3\)-collisions at once, and generalizing beyond \(k=3\) – laid out in a companion note, which argues this is the most tractable single piece: the only one whose resolution needs no new proof technique in either direction, closing what it calls the smallest open quantity in the family.
Parameter lattice
Two independent axes: how a program may query (oblivious sequential, oblivious parallel, or fully adaptive) and how many disjoint \(3\)-collisions it must produce. Only one cell has a statement on the site so far; the rest are real, posed questions from the companion note that have not yet been turned into their own leaves.
| single \(3\)-collision | \(C\) disjoint \(3\)-collisions | |
|---|---|---|
| oblivious, sequential | c/0007 – open | unstated |
| oblivious, parallel | unstated | unstated |
| adaptive (fully general) | unstated | unstated |
This is itself a small slice of a larger family the companion note develops – general \(k\), cumulative-memory measures, and a register-machine model – none of which has a leaf here yet.