Advertisement
Published in:
2006 | OriginalPaper | Chapter
Birthday Paradox for Multi-collisions
Authors : Kazuhiro Suzuki, Dongvu Tonien, Kaoru Kurosawa, Koji Toyota
Published in: Information Security and Cryptology – ICISC 2006
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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
×
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.