Welcome to the resource topic for 2009/305
Title:
Improved generic algorithms for 3-collisions
Authors: Antoine Joux, 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.
ePrint: https://eprint.iacr.org/2009/305
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .