ほぼ数式です。勉強会の補遺です。
教科書の不等式がそのままでは成り立たなさそうなので、少し変形してあります。
注意：$\log$の底は2とする。
内容としては、暗号におけるprivacy amplification(秘匿性増幅)に関連する定理です。
定義 (universal hash functions)
集合$\mathcal{A}$から集合$\mathcal{B}$への関数の族$\mathcal{G}$を考える。
もし、$g \in \mathcal{G}$が一様に選ばれた時、任意の$a_1, a_2 \neq a_1 \in \mathcal{A}$に対して衝突する確率、つまり
${\rm Pr}\{G(a_1) = G(a_2)\} = \sum_{g \in \mathcal{G}}\Pr\{G=g\}Pr\{g(a_1)=g(a_2)\}$ が高々 $1 / |\mathcal{B}|$ であるとき、$\mathcal{G}$をuniversalであるという。
定義 (collision entropy)
確率変数$X$に対して、その確率質量関数を$p(x)$とすると、collision entropy$H_c(X)$は
$$
\begin{align}
H_c(X) &:= - \log \left[\sum_x p(x)^2\right] = -\log \left[ E[p(X)] \right ]
\end{align}
$$
と定義される。
Lemma
$H_c(X) \leq H(X)$
proof
$-\log$ が下に凸であることと、Jensenの不等式から明らか。
定義 (conditional collision entropy)
確率変数$X, Y$に対して、その確率質量関数を$p(x, y)$とする。ここで、conditional collision entropy$H_c(Y|X)$を
$$
H_c(Y|X) := \sum_x p(x) H_c(Y | X = x)
$$
ここで、
$$
H_c(Y | X = x) := - \log \left[\sum_y p(y|x)^2\right]
$$
と定義する。
Thorem 12.16(の修正版)
$X$をアルファベット$\mathcal{X}$上の確率変数、$G$を$\mathcal{X}$から$\{0, 1\}^m$へのあるuniversal hash functions上の一様分布に従う確率変数とする。このとき
$$
H(G(X)|G) \geq H_c(G(X) | G) \geq m - \frac{2^{m - H_c(X)}}{ln 2}
$$
が成り立つ。
proof
左の不等式は、Lemmaから直ちに成り立つ。
右の不等式について証明する。
$$
H_c(G(X) | G) = \sum_g\Pr\{G=g\} H_c(g(X) | G = g)\\
H_c(g(X) | G = g) = - \log\left[\sum_{y \in \{0, 1\}^m} \Pr\{g(X) = y\}^2\right]
$$
である。$- \log$が下に凸であることとJensenの不等式から、
$$
\begin{align}
H_c(G(X) | G) & = - \sum_g\Pr\{G=g\}\log\left[\sum_{y \in \{0, 1\}^m} \Pr\{g(X) = y\}^2\right] \\
&\geq - \log\left[\sum_g\Pr\{G=g\}\sum_{y \in \{0, 1\}^m} \Pr\{g(X) = y\}^2\right]
\end{align}
$$
が成り立つ。ここで、$X_1$と$X_2$を$X$に従う独立な確率変数とすると
$$
\begin{align}
\sum_{y \in \{0, 1\}^m}\Pr\{g(X) = y\}^2 & = \Pr\{g(X_1) = g(X_2)\}\\
& = \Pr\{X_1 = X_2\} + \Pr\{X_1 \neq X_2\}\Pr\{g(X_1) = g(X_2) |X_1 \neq X_2 \}
\end{align}
$$
ここで、衝突確率$P_c(X)$を
$$
P_c(X) := \sum_xp(x)^2 = \Pr\{X_1 = X_2\}
$$
と定義し、universal hash functionsの定義から、
$$
\sum_g\Pr\{G=g\}\Pr\{g(X_1) = g(X_2) |X_1 \neq X_2 \} \leq 1 / |\{0, 1\}^m| = 2^{-m}
$$
に注意すると、
$$
\begin{align}
\sum_g\Pr\{G=g\}\sum_{y \in \{0, 1\}^m}\Pr\{g(X) = y\}^2 & \leq P_c(X) + (1 - P_c(X))2^{-m} \\
& = (1 - 2^{-m}) P_c(X) + 2^{-m} \\
& \leq P_c(X) + 2^{-m} \\
& = 2^{-H_c(X)} + 2^{-m} \\
& = 2^{-m}(1 + 2^{m-H_c(X)})
\end{align}
$$
これと、$-log$が単調減少関数であることから
$$
H_c(g(X) | G ) \geq m - \log(1 + 2^{m-H_c(X)})
$$
また、$ln(1 + x) \leq x$であることから、
$$
H_c(g(X) | G ) \geq m - \frac{2^{m-H_c(X)}}{ln 2}
$$
が成り立つ。
参考文献
C. H. Bennett, G. Brassard, C. Crépeau, and U. M. Maurer. Generalized privacyamplification. IEEE Trans. Inf. Theory, 41:1915–1923, 1995.