Skip to main content
placeholder image

Birthday paradox for multi-collisions

Journal Article


Abstract


  • n 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-s≈Q, 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/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.

Authors


  •   Suzuki, Kazuhiro (external author)
  •   Tonien, Joseph
  •   Kurosawa, Kaoru (external author)
  •   Toyota, Koji (external author)

Publication Date


  • 2008

Citation


  • Suzuki, K., Tonien, D., Kurosawa, K. & Toyota, K. (2008). Birthday paradox for multi-collisions. IEICE Transactions on Information and Systems, 91A (1), 39-45.

Number Of Pages


  • 6

Start Page


  • 39

End Page


  • 45

Volume


  • 91A

Issue


  • 1

Place Of Publication


  • Japan

Abstract


  • n 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-s≈Q, 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/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.

Authors


  •   Suzuki, Kazuhiro (external author)
  •   Tonien, Joseph
  •   Kurosawa, Kaoru (external author)
  •   Toyota, Koji (external author)

Publication Date


  • 2008

Citation


  • Suzuki, K., Tonien, D., Kurosawa, K. & Toyota, K. (2008). Birthday paradox for multi-collisions. IEICE Transactions on Information and Systems, 91A (1), 39-45.

Number Of Pages


  • 6

Start Page


  • 39

End Page


  • 45

Volume


  • 91A

Issue


  • 1

Place Of Publication


  • Japan