Universal Hash Family — Jemoka Knowledge Base

\begin{equation} H = \left\{h: \left\{0,1\right\}^{h} \to \left\{0,1\right\}^{k}\right\} \end{equation}

properties of pairwise independence: 1 wise independent: \forall y, \forall a, P_{h \sim H}\left[h\left(y\right) = a\right] = 2^{-k} 2 wise independent: \forall y \neq y’, P_{h \sim H}\left[h\left(y\right) = h\left(y’\right)\right] = 2^{-k} You will notice that this is not full randomness, just that there are some amount of randomness. requirements For all u_{i}, u_{j} \in U in the universe, n buckets in terms of desired randomness, with u_{i} \neq u_{j}, then:

\begin{equation} P_{h\in H} \left\{h\left(u_{i}\right) = h\left(u_{j}\right)\right\} \leq \frac{1}{n} \end{equation}

A universal hash family is 2-wise indpendent additional information example of universal hash family Pick prime p \geq M (for size of universe M = |U|); define:

\begin{align} f_{a,b}\left(x\right) = ax + b\ \text{mod}\ p \end{align}

\begin{equation} h_{a,b}\left(x\right) = f_{a,b}\left(x\right)\ \text{mod}\ n \end{equation}

Our hash family is determined by:

\begin{equation} H = \left\{h_{a,b}\left(x\right) \mid a \in \left\{1, \dots, p-1\right\}, b \in \left\{0, \dots, p-1\right\}\right\} \end{equation}

The above hash family takes O\left(\log M\right) to store We have p\left(p-1\right) choices for a,b, and since p \geq M, we have |H| = O\left(M^{2}\right). Storing a,b takes \log \left(p\right) bits to store, which gives 2\log \left(p\right) = O\left(\log\left(M\right)\right) bits to store if p \sim M. Note also that h is decently fast to evaluate. This gives O\left(n\right) buckets, O\left(n\right) items with \log \left(M\right) bits per item (because we need to ID each item wrt universe), and O\left(\log M\right) to store the hash function. example of 1/2-wise independence Let’s pick k strings r^{(1)} … r^{(k)} \sim \left\{0,1\right\}^{n} uniform random things, and k bits b_{1}, …, b_{k} \sim \left\{0,1\right\} uniform random bits. This is O\left(kn\right) bits of randomness.

\begin{equation} h\left(y\right) = \left(r^{(1)}y + b_1, r^{(2)} y + b_2, \dots, r^{(k)} y + b_{k}\right) \end{equation}

This is 1-wise random due to the randomness of b_{j}, since will shift into 2^{-k} random. For 2 wise independenec