Paper 2009/305

Improved generic algorithms for 3-collisions

Antoine Joux and Stefan Lucks

Abstract

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-parallelisable algorithms are known. The current paper describes memory-efficient and parallelisable algorithms for $r\ge 3$. The main results are: (1)~A sequential algorithm for 3-collisions, roughly using memory $N^{\alpha }$ and time $N^{1-\alpha }$ for $\alpha \le 1/3$. I.e., given $N^{1/3}$ units of storage, on can find 3-collisions in time $N^{2/3}$. Note that there is a time-memory tradeoff which allows to reduce the memory consumption. (2)~A parallelisation of this algorithm using $N^{1/3}$ processors running in time $N^{1/3}$. Each single processor only needs a constant amount of memory. (3)~An generalisation of this second approach to $$-collisions for $$: given $$ parallel processors, on can generate $$-collisions roughly in time $$, using memory $$ on every processor.