Paper 2009/305
Improved generic algorithms for 3collisions
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^{(r1)/r} $ units of time on a sequential machine. For $r$=2, memoryless and wellparallelisable algorithms are known. The current paper describes memoryefficient and parallelisable algorithms for $r \ge 3$. The main results are: (1)~A sequential algorithm for 3collisions, 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 3collisions in time $N^{2/3}$. Note that there is a timememory 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^{((r1)/r)s}$, using memory $N^{((r2)/r)s}$ on every processor.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 multicollisionrandom maps
 Contact author(s)
 Antoine Joux @ m4x org
 History
 20090624: received
 Short URL
 https://ia.cr/2009/305
 License

CC BY
BibTeX
@misc{cryptoeprint:2009/305, author = {Antoine Joux and Stefan Lucks}, title = {Improved generic algorithms for 3collisions}, howpublished = {Cryptology ePrint Archive, Paper 2009/305}, year = {2009}, note = {\url{https://eprint.iacr.org/2009/305}}, url = {https://eprint.iacr.org/2009/305} }