2006 | OriginalPaper | Buchkapitel
Birthday Paradox for Multi-collisions
verfasst von : Kazuhiro Suzuki, Dongvu Tonien, Kaoru Kurosawa, Koji Toyota
Erschienen in: Information Security and Cryptology – ICISC 2006
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.