Improved Generic Algorithms for 3-Collisions

Zusammenfassung

An r-collision for a function is a set of r distinct inputs with identical outputs. Actually finding r-collisions for a random map over a finite set of cardinality N requires at least about N (r − 1)/r units of time on a sequential machine. For r=2, memoryless and well-parallelizable algorithms are known. The current paper describes memory-efficient and parallelizable algorithms for r ≥ 3. The main results are: (1) A sequential algorithm for 3-collisions, roughly using memory N α and time N 1 − α for α ≤ 1/3. In particular, given N 1/3 units of storage, one can find 3-collisions in time N 2/3. (2) A parallelization of this algorithm using N 1/3 processors running in time N 1/3, where each single processor only needs a constant amount of memory. (3) A generalisation of this second approach to r-collisions for r ≥ 3: given N s parallel processors, with s ≤ (r − 2)/r, one can generate r-collisions roughly in time N ((r − 1)/r) − s, using memory N ((r − 2)/r) − s on every processor.