暗号理論の問題

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

攻撃者は互いに異なる $5$ 個の入力 $m_1,m_2,\dots ,m_5$ についてハッシュ値 $H(m_1),\dots ,H(m_5)$ を計算する。このとき、ある値 $v$ について $H(m_i)=v$ となる $i$ が $3$ 個以上存在する確率を求めよ。この事象を「$3$ 重衝突（3-マルチコリジョン）が起こる」という。

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

攻撃者は互いに異なる $k$ 個の入力 $m_1,m_2,\dots ,m_k$ を用意し、それぞれのハッシュ値 $H(m_1),H(m_2),\dots ,H(m_k)$ を計算する（$k$ は正の整数）。この $k$ 個のハッシュ値の中に等しいものが少なくとも $1$ 組ある（衝突が起こる）確率が $\frac{1}{2}$ を超えるような $k$ のうち、最小のものを求めよ。

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

互いに異なる $k$ 個の入力（$k$ は正の整数）のハッシュ値を計算したとき、少なくとも $1$ 組の衝突（同じハッシュ値をもつ $2$ つの入力）が起こる確率を $p_k$ とする。$p_k$ を近似式
$$p_k\approx 1-e^{-\frac{k(k-1)}{2N}}$$
で見積もる。この近似値が $\frac{1}{2}$ 以上となる最小の正の整数 $k$ を求めよ。ただし、$\log 2=0.6931$ として計算してよい（$\log$ は自然対数）。

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

互いに異なる $k$ 個の入力 $m_1,m_2,\dots ,m_k$ のハッシュ値のうち、少なくとも $2$ つが一致する（衝突が起こる）確率 $p_k$ を、近似式
$$p_k\approx 1-e^{-\frac{k(k-1)}{2N}}$$
で見積もる。この近似値が $\frac{1}{2}$ 以上となる最小の正の整数 $k$ を求めよ。ただし、$\log 2=0.693$ として計算してよい（$\log$ は自然対数）。

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

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