Universal hash function

Definition

Let the Universal Hashing function $F$ be defined as a family or set of functions $f$ which maps $\{0,1\}^{n}\rightarrow \{0,1\}^{m}$, where for any $x,y\in \{0,1\}^{n}$,$x\neq y$ and $x^{'},y^{'}\in \{0,1\}^{m}$.

The probability that $f\in F$ which follows from this construction is given by $Prob_{f\in F}[f\left(x\right)=x^{'}\wedge f\left(y\right)=y^{'}]={\frac {1}{2^{2m}}}$

The implication of such a hashing function is that collisions only happen with the above given probability. Thus yielding an average case performance even if the keys are carefully chosen.

Example

For $A\in \{0,1\}^{m\times n},b\in \{0,1\}^{m}$ and $f_{A,b}:\{0,1\}^{n}\rightarrow \{0,1\}^{m}$.

Let the universal hashing function $F=\{f_{A,b}:A\in \{0,1\}^{m\times n},b\in \{0,1\}^{m}\}$ where $f_{A,b}\left(x\right)=Ax+b,\forall x\in \{0,1\}^{n}$

References

Wolfram