Improved Generic Algorithms for 3-Collisions

摘要

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.