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)) 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)). Thus the above folklore is wrong for large s. We next show that if s is small, so that we can assume Q - s≈ Q, then this probability is at least 1/s! - l/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/s) × Q + 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.
展开▼
