Lesson 1

Universal Hashing

For finite sets \(X,Y\), let \(Y^{X}\) denote the set of all functions from \(X\) to \(Y\). A family of functions \(\mathcal{H}\subseteq Y^{X}\) is called universal if for any \(x \neq x' \in X\) \[\Pr[h(x)=h(x')]\le \frac{1}{|Y|}\ ,\] where \(h\) is chosen randomly (and uniformly) from \(\mathcal{H}\). A family \(\mathcal{H}\subseteq Y^{X}\) is called strongly universal (or 2-universal) if for any \(x \neq x' \in X\) and any \(y,y' \in Y\) \[\Pr[h(x)=y,\ h(x')=y']=\frac{1}{|Y|^2}\ .\] It is easy to see that strong universality is indeed a stronger property: \[\Pr[h(x)=h(x')]=\sum_{y \in Y}\Pr[h(x)=y,\ h(x')=y]=\frac{1}{|Y|}\ .\]

From the definition of strong universality, it follows that the events \(h(x)=y\) and \(h(x')=y'\) are independent. To show this, it is sufficient to prove that for any \(x \in X\) and \(y \in Y\) \[\Pr[h(x)=y]=\frac{1}{|Y|}\ .\] Let us fix an arbitrary \(x' \in X\) such that \(x' \neq x\). Then \[\begin{align*}\Pr[h(x)=y]&=\sum_{y' \in Y}\Pr[h(x)=y,\ h(x')=y']\\&=\frac{1}{|Y|}\ .\end{align*}\]

Now, let us construct a strongly universal family.

Theorem. Let \(\mathbb{F}\) be a finite field, and let \(a, b \in \mathbb{F}\) be any two of its elements. Define the function \(f_{a,b}\colon \mathbb{F} \to \mathbb{F}\) as follows: \(f_{a,b}(x)=ax+b\). Then the family of functions \[\mathcal{F}=\{f_{a,b}\colon a, b \in \mathbb{F}\}\] is 2-universal.

Proof. Let \(x \neq x', y, y' \in \mathbb{F}\). Then \[\begin{align*}\Pr[h(x)=y,\ h(x')=y']&=\Pr[ax+b=y,\ ax'+b=y']=\\&=\Pr\left[a=\frac{y'-y}{x'-x}, \ b=y-\frac{y'-y}{x'-x}\cdot x\right]=\\&=\frac{1}{|\mathbb{F|^2}}\ .\end{align*}\]◼