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\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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
multicollisionrandom maps
Contact author(s)
Antoine Joux @ m4x org
History
2009-06-24: received
Short URL
https://ia.cr/2009/305
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/305,
      author = {Antoine Joux and Stefan Lucks},
      title = {Improved generic algorithms for 3-collisions},
      howpublished = {Cryptology ePrint Archive, Paper 2009/305},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/305}},
      url = {https://eprint.iacr.org/2009/305}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.