さて問題 - 186 @ hatenablog

$l(n) \leq cn (c < 1)$ としておく。
で、 $\mathcal{A}:\{0,1\}^n$ , $\mathcal{Z}:\{0,1\}^{l(n)}$ , $\mathcal{H}:$ family of Hash function $\mathcal{A}$ to $\mathcal{Z}$ とする。
the Leftover Hash Lemmaを適用して、
$(H,H(A)):$ $\delta$ -Universal on $\mathcal{H} \time \mathcal{Z}$ で、
$\delta \leq \frac{\sqrt{2^{-n} 2^{l(n)}}}{2} \leq \frac{2^{-\frac{1-c}{2}n}}{2}$
$\delta$ -Universal の定義から
$\delta = \frac{1}{2}\Bigsum_{(h,h(a)) \in \mathcal{H} \time \mathcal{H}(A) } |Pr[(H,H(A)) = (h,h(a))] - \frac{1}{2^{l(n)}}| \leq \frac{2^{-\frac{1-c}{2}n}}{2}$
よって、
$\Bigsum_{(h,h(a)) \in \mathcal{H} \time \mathcal{H}(A) } |Pr[(H,H(A)) = (h,h(a))] - \frac{1}{2^{l(n)}}| \leq 2^{-\frac{1-c}{2}n}$