**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\le1/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 $r$-collisions for $r \ge3$: given $N^s$ parallel processors, on can generate $r$-collisions roughly in time $N^{((r-1)/r)-s}$, using memory $N^{((r-2)/r)-s}$ on every processor.

**Category / Keywords: **foundations / multicollision, random maps

**Date: **received 23 Jun 2009

**Contact author: **Antoine Joux at m4x org

**Available format(s): **PDF | BibTeX Citation

**Version: **20090624:072015 (All versions of this report)

**Short URL: **ia.cr/2009/305

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]