Birthday Paradox for Multi-Collisions

Kazuhiro SUZUKI  Dongvu TONIEN  Kaoru KUROSAWA  Koji TOYOTA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E91-A   No.1   pp.39-45
Publication Date: 2008/01/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e91-a.1.39
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Hash Functions
hash function,  birthday paradox,  multi-collision,  collision resistant,  

Full Text: PDF>>
Buy this Article

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! for any s, which is very small for large s (for example, s=n(s-1)/s). Thus the above folklore is wrong for large s. We next show that if s is small, so that we can assume Q-sQ, then this probability is at least 1/s!-1/2(s!)2, which is very high for small s (for example, s is a constant). Thus the above folklore is true for small s. Moreover, we show that by hashing (s!)1/sQ+s-1 (≤ n) times, an s-collision is found with probability approximately 0.5 for any n and s such that (s!/n)1/s ≈ 0. Note that if s=2, it coincides with the usual birthday paradox. Hence it is a generalization of the birthday paradox to multi-collisions.