In this paper, we study multi-collision probability. For a hash function H: D→ R with |R| = n, it has been believed that we can find an s-collision by hashing Q = n (s-1)/s  times. We first show that this probability is at most 1/s! which is very small for large s. We next show that by hashing (s!) 1/s  x Q times, an s-collision is found with probability approximately 0.5 for sufficiently large n. Note that if s = 2, it coincides with the usual birthday paradox. Hence it is a generalization of the birthday paradox to multi-collisions.
['Kazuhiro Suzuki', 'Dongvu Tonien', 'Kaoru Kurosawa', 'Koji Toyota']
Birthday paradox for multi-collisions