講演抄録/キーワード |
講演名 |
2007-05-18 12:50
Multi-Collisionに関するバースディパラドックスについて ○鈴木一弘(茨城大)・ドン トニエン(ウォロンゴン大)・黒澤 馨・豊田貢司(茨城大) ISEC2007-6 |
抄録 |
(和) |
ハッシュ関数$H:D \rightarrow R$($|R|=n$)のmulti-collision(多重衝突)について、
従来は$Q=n^{(s-1)/s}$回のハッシュ計算で
確率的に1個の$s$-collision、
すなわちハッシュ値が等しい$s$個の入力メッセージが見つかるだろうと信じられていた。
本論文では、その確率が高々$1/s!$であり、
大きな$s$に対しては上記の主張が成り立たないことを示す。
一方、十分大きな$n$に対して、$(s!)^{1/s} \times Q$回のハッシュ計算ならば
$s$-collisionが確率1/2で起きることを示す。
この確率は、$s=2$とするとよく知られたバースデイパラドックスとなっているため、
本論文はバースデイパラドックスのmulti-collisionへの一般化となっている。 |
(英) |
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. |
キーワード |
(和) |
ハッシュ関数 / バースデイパラドックス / 多重衝突 / 衝突耐性 / / / / |
(英) |
hash function / birthday paradox / multi-collision / collision resistant / / / / |
文献情報 |
信学技報, vol. 107, no. 44, ISEC2007-6, pp. 39-44, 2007年5月. |
資料番号 |
ISEC2007-6 |
発行日 |
2007-05-11 (ISEC) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
ISEC2007-6 |