2 The universal-hashing independence estimate

Definition 6 \((\varepsilon ,A,B)\)-independence; Definition 3

Let \(A \subseteq \{ 0,1\} ^n\), \(B \subseteq \{ 0,1\} ^m\), \(h:\{ 0,1\} ^n \to \{ 0,1\} ^m\), and \(\varepsilon {\gt}0\). Write \(\mu (A)=|A|/2^n\) and \(\mu (B)=|B|/2^m\). The function \(h\) is \((\varepsilon ,A,B)\)-independent if

\[ \left|\operatorname {Pr}_{x \leftarrow \{ 0,1\} ^n}[x \in A \text{ and } h(x)\in B] -\mu (A)\mu (B)\right|\le \varepsilon . \]

Lemma 7 Matrix encoding of a hash event

Let \(\mathcal{H}\) be universal, \(A \subseteq \{ 0,1\} ^n\), and \(B \subseteq \{ 0,1\} ^m\). For \(M(x,h)=1\) if \(h(x)\in B\) and \(M(x,h)=0\) otherwise, define \(f(h)=\mathbb {E}_{x \leftarrow A}M(x,h)\) and \(p=\mu (B)\). Then \(\mathbb {E}_{h \leftarrow \mathcal{H}}f(h)=p\), and \(h\) is \((\varepsilon ,A,B)\)-independent exactly when \(\left|p-f(h)\right|\le \varepsilon /\mu (A)\).

Proof ▶

For each fixed \(x\), universality implies that \(h(x)\) is uniform on \(\{ 0,1\} ^m\), because the one-point marginal of a two-universal family is uniform. Hence \(\mathbb {E}_h M(x,h)=p\) for every \(x\), and averaging over \(x \in A\) gives \(\mathbb {E}_h f(h)=p\). Also

\[ \operatorname {Pr}_{x \leftarrow \{ 0,1\} ^n}[x\in A,\ h(x)\in B] =\mu (A)\operatorname {Pr}_{x \leftarrow A}[h(x)\in B]=\mu (A)f(h). \]

Substituting this identity into Definition 6 and dividing by \(\mu (A)\) gives the stated equivalence.

Lemma 8 Variance of the hash event average

With the notation of Lemma 7,

\[ \operatorname {Var}_{h \leftarrow \mathcal{H}}(f(h))=\frac{\mu (B)(1-\mu (B))}{|A|}. \]

Proof ▶

Expanding the variance and using \(\mathbb {E}_h f(h)=p\),

\[ \operatorname {Var}(f)=\mathbb {E}_{x_1,x_2 \leftarrow A}\mathbb {E}_h M(x_1,h)M(x_2,h)-p^2 . \]

If \(x_1 \ne x_2\), universality gives independent uniform values \(h(x_1)\) and \(h(x_2)\), so the inner expectation is \(p^2\). If \(x_1=x_2\), then \(M(x_1,h)M(x_2,h)=M(x_1,h)\) and the inner expectation is \(p\). The equal case has probability \(1/|A|\) under the uniform choice from \(A \times A\). Therefore

\[ \operatorname {Var}(f)=\left(1-\frac1{|A|}\right)p^2+\frac1{|A|}p-p^2 =\frac{p(1-p)}{|A|}. \]

Lemma 9 Chebyshev conversion

With the notation of Lemma 8, for every \(\delta {\gt}0\),

\[ \operatorname {Pr}_{h \leftarrow \mathcal{H}}\big[\left|p-f(h)\right|\ge \delta \big] \le \frac{\mu (B)(1-\mu (B))}{|A|\delta ^2}. \]

Proof ▶

Chebyshev’s inequality applied to the random variable \(f(h)\) gives \(\operatorname {Pr}[\left|f-\mathbb {E}f\right|\ge \delta ]\le \operatorname {Var}(f)/\delta ^2\). Since \(\mathbb {E}f=p\) and Lemma 8 evaluates \(\operatorname {Var}(f)\), the displayed bound follows.

Lemma 10 Universal hash independence bound; Lemma 1

Let \(A \subseteq \{ 0,1\} ^n\), \(B \subseteq \{ 0,1\} ^m\), let \(\mathcal{H}\) be a universal family of functions \(\{ 0,1\} ^n \to \{ 0,1\} ^m\), and let \(\varepsilon {\gt}0\). Then

\[ \operatorname {Pr}_{h \leftarrow \mathcal{H}} [h \text{ is not }(\varepsilon ,A,B)\text{-independent}] \le \frac{\mu (A)\mu (B)(1-\mu (B))}{2^n\varepsilon ^2}. \]

Proof ▶

By Lemma 7, failure of \((\varepsilon ,A,B)\)-independence is the event \(\left|p-f(h)\right|{\gt}\varepsilon /\mu (A)\). Apply Lemma 9 with \(\delta =\varepsilon /\mu (A)\). Since \(|A|=2^n\mu (A)\), the right hand side becomes

\[ \frac{\mu (B)(1-\mu (B))}{|A|}\cdot \frac{\mu (A)^2}{\varepsilon ^2} =\frac{\mu (A)\mu (B)(1-\mu (B))}{2^n\varepsilon ^2}. \]