# Nielsen Chuang Thm 12.16について

暗号における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] が高々 $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.

[^1]: この場合、$\Pr\{g(a_1)=g(a_2)\}$は関数的なので$0, 1$のどちらかの値をとる。