| Paper Abstract and Keywords |
| Presentation |
2007-05-18 12:50
Birthday Paradox for Multi-Collisions
Kazuhiro Suzuki (Ibaraki Univ.), Dongvu Tonien (Uni.y of Wollongong), Kaoru Kurosawa, Koji Toyota (Ibaraki Univ.) |
| Abstract |
(in Japanese) |
(See Japanese page) |
| (in English) |
In this paper, we study multi-collision probability.
For a hash function $H:D \rightarrow 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} \times 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. |
| Keyword |
(in Japanese) |
(See Japanese page) |
| (in English) |
hash function / birthday paradox / multi-collision / collision resistant / / / / |
| Reference Info. |
IEICE Tech. Rep., vol. 107, no. 44, ISEC2007-6, pp. 39-44, May 2007. |
| Paper # |
ISEC2007-6 |
| Conference Information |
| Committee |
ISEC |
| Conference Date |
2007-05-18 - 2007-05-18 |
| Place (in Japanese) |
(See Japanese page) |
| Place (in English) |
Kikai-Shinko-Kaikan Bldg. |
| Topics (in Japanese) |
ˆê”Ê |
| Topics (in English) |
|
| Paper Information |
| Registration To |
ISEC |
| Conference Code |
2007-05-ISEC |
| Language |
Japanese |
| Title (in Japanese) |
(See Japanese page) |
| Sub Title (in Japanese) |
(See Japanese page) |
| Title (in English) |
Birthday Paradox for Multi-Collisions |
| Sub Title (in English) |
|
| Keyword(1) |
hash function |
| Keyword(2) |
birthday paradox |
| Keyword(3) |
multi-collision |
| Keyword(4) |
collision resistant |
| Keyword(5) |
|
| Keyword(6) |
|
| Keyword(7) |
|
| Keyword(8) |
|
| 1st Author's Name |
Kazuhiro Suzuki |
| 1st Author's Affiliation |
Ibaraki University (Ibaraki Univ.) |
| 2nd Author's Name |
Dongvu Tonien |
| 2nd Author's Affiliation |
University of Wollongong (Uni.y of Wollongong) |
| 3rd Author's Name |
Kaoru Kurosawa |
| 3rd Author's Affiliation |
Ibaraki University (Ibaraki Univ.) |
| 4th Author's Name |
Koji Toyota |
| 4th Author's Affiliation |
Ibaraki University (Ibaraki Univ.) |
| 5th Author's Name |
|
| 5th Author's Affiliation |
() |
| 6th Author's Name |
|
| 6th Author's Affiliation |
() |
| 7th Author's Name |
|
| 7th Author's Affiliation |
() |
| 8th Author's Name |
|
| 8th Author's Affiliation |
() |
| 9th Author's Name |
|
| 9th Author's Affiliation |
() |
| 10th Author's Name |
|
| 10th Author's Affiliation |
() |
| 11th Author's Name |
|
| 11th Author's Affiliation |
() |
| 12th Author's Name |
|
| 12th Author's Affiliation |
() |
| 13th Author's Name |
|
| 13th Author's Affiliation |
() |
| 14th Author's Name |
|
| 14th Author's Affiliation |
() |
| 15th Author's Name |
|
| 15th Author's Affiliation |
() |
| Speaker |
1 |
| Date Time |
2007-05-18 12:50:00 |
| Presentation Time |
25 |
| Registration for |
ISEC |
| Paper # |
IEICE-ISEC2007-6 |
| Volume (vol) |
IEICE-107 |
| Number (no) |
IEICE-ISEC-44 |
| Page |
pp.39-44 |
| #Pages |
IEICE-6 |
|