この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

暗号理論の問題

難易度 3期末試験の応用レベル大学数学暗号理論

出力が $4$ 通りの値 ${0, 1, 2, 3}$ のどれかになるハッシュ関数 $H$ を考える。 $H$ はランダムオラクルとみなし、互いに異なる入力に対する出力は、それぞれ独立に $4$ 通りの値から等確率で選ばれるものとする。

攻撃者は互いに異なる入力 $m_{1}, m_{2}, m_{3}, \dots$ をこの順に $1$ つずつ $H$ に問い合わせ、それまでに得た出力のどれかと同じ出力が初めて得られた時点で問い合わせをやめる。すなわち、
$H (m_{t}) = H (m_{s}) となる s < t が存在する最小の正の整数 t$
を $T$ とし、攻撃者は $T$ 回問い合わせる。 $T$ の期待値 $E [T]$ を求めよ。

この問題で使うもの

ハッシュの衝突確率（誕生日問題）（説明と入口の問題）
確率の定義と和事象・余事象（説明と入口の問題）

この問題を解けるようになるまで（58 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

「最初の $k$ 回の出力がすべて異なる」確率 $P (T > k)$ を考えると、 $T$ の分布が求めやすくなります。

ヒント 2

$P (T > k) = \prod_{i = 0}^{k - 1} (1 - \frac{i}{4})$ です。出力は $4$ 通りなので $T$ は $2$ 以上 $5$ 以下の値しかとりません。

ヒント 3

$P (T > 2) = \frac{3}{4}$ , $P (T > 3) = \frac{3}{8}$ , $P (T > 4) = \frac{3}{32}$ です。 $P (T = t) = P (T > t - 1) - P (T > t)$ から分布を求め、期待値を計算しましょう。

答えと解説

答えを見る

\frac{103}{32}

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

$N = 4$ とする。最初の $k$ 回の出力 $H (m_{1}), \dots, H (m_{k})$ がすべて異なる確率は、各出力が独立に等確率であることから
$P (T > k) = \frac{N}{N} \cdot \frac{N - 1}{N} \dots \frac{N - k + 1}{N} = i = 0 \prod k - 1 (1 - \frac{i}{N})$
である（ $T > k$ は「最初の $k$ 回では衝突が起きていない」ことと同じ）。出力は $4$ 通りしかないので、鳩の巣原理により $5$ 回問い合わせれば必ず衝突し、 $2 \leq T \leq 5$ である。

具体的に計算すると
$P (T > 1) = 1, P (T > 2) = \frac{3}{4}, P (T > 3) = \frac{3}{4} \cdot \frac{2}{4} = \frac{3}{8}, P (T > 4) = \frac{3}{8} \cdot \frac{1}{4} = \frac{3}{32}, P (T > 5) = 0.$
よって各値をとる確率は $P (T = t) = P (T > t - 1) - P (T > t)$ より
$P (T = 2) = 1 - \frac{3}{4} = \frac{8}{32}, P (T = 3) = \frac{3}{4} - \frac{3}{8} = \frac{12}{32},$
$P (T = 4) = \frac{3}{8} - \frac{3}{32} = \frac{9}{32}, P (T = 5) = \frac{3}{32} .$
合計は $\frac{8 + 12 + 9 + 3}{32} = 1$ で確かに確率分布になっている。したがって
$E [T] = 2 \cdot \frac{8}{32} + 3 \cdot \frac{12}{32} + 4 \cdot \frac{9}{32} + 5 \cdot \frac{3}{32} = \frac{16 + 36 + 36 + 15}{32} = \frac{103}{32} .$

（別解） $0$ 以上の整数値をとる確率変数について $E [T] = \sum_{k = 0}^{\infty} P (T > k)$ が成り立つので
$E [T] = 1 + 1 + \frac{3}{4} + \frac{3}{8} + \frac{3}{32} = \frac{32 + 32 + 24 + 12 + 3}{32} = \frac{103}{32} .$

別解

$T$ は 2 以上 5 以下の整数値をとる（出力は 4 通りしかないので、5 回目までに必ず衝突する）。 $E [T] = \sum_{k \geq 0} P (T > k)$ を用いる。 $T > k$ は「最初の $k$ 回の出力がすべて異なる」ことと同値。\n\n- $P (T > 0) = 1$ \n- $P (T > 1) = 1$ \n- $P (T > 2) = \frac{3}{4}$ \n- $P (T > 3) = \frac{3}{4} \cdot \frac{2}{4} = \frac{3}{8}$ \n- $P (T > 4) = \frac{3}{4} \cdot \frac{2}{4} \cdot \frac{1}{4} = \frac{3}{32}$ \n- $P (T > 5) = 0$ \n\nよって $E [T] = 1 + 1 + \frac{3}{4} + \frac{3}{8} + \frac{3}{32} = \frac{32 + 32 + 24 + 12 + 3}{32} = \frac{103}{32}$ 。\n\n検算: $P (T = 2) = \frac{1}{4}$ , $P (T = 3) = \frac{3}{4} \cdot \frac{2}{4} = \frac{3}{8}$ , $P (T = 4) = \frac{3}{8} \cdot \frac{3}{4} = \frac{9}{32}$ , $P (T = 5) = \frac{3}{32}$ 。合計 $\frac{8 + 12 + 9 + 3}{32} = 1$ ✓。 $E [T] = 2 \cdot \frac{8}{32} + 3 \cdot \frac{12}{32} + 4 \cdot \frac{9}{32} + 5 \cdot \frac{3}{32} = \frac{16 + 36 + 36 + 15}{32} = \frac{103}{32}$ ✓。

暗号理論の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題