[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / raw/concept/kbhuniversal_hash_family.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "Universal Hash Family" source: https://www.jemoka.com/posts/kbhuniversal_hash_family/ --- \begin{equation} H = \qty {h: \qty {0,1}^{h} \to \qty {0,1}^{k}} \end{equation} properties of pairwise independence: 1 wise independent: \(\forall y, \forall a\), \(P_{h \sim H}\qty [h\qty(y) = a] = 2^{-k}\) 2 wise independent: \(\forall y \neq y’\), \(P_{h \sim H}\qty [h\qty(y) = h\qty(y’)] = 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} \qty {h\qty(u_{i}) = h\qty(u_{j})} \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}\qty(x) = ax + b\ \text{mod}\ p \end{align} \begin{equation} h_{a,b}\qty(x) = f_{a,b}\qty(x)\ \text{mod}\ n \end{equation} Our hash family is determined by: \begin{equation} H = \qty {h_{a,b}\qty(x) \mid a \in \qty {1, \dots, p-1}, b \in \qty {0, \dots, p-1}} \end{equation} The above hash family takes \(O\qty(\log M)\) to store We have \(p\qty(p-1)\) choices for \(a,b\), and since \(p \geq M\), we have \(|H| = O\qty(M^{2})\). Storing \(a,b\) takes \(\log \qty(p)\) bits to store, which gives \(2\log \qty(p) = O\qty(\log\qty(M))\) bits to store if \(p \sim M\). Note also that \(h\) is decently fast to evaluate. This gives \(O\qty(n)\) buckets, \(O\qty(n)\) items with \(\log \qty(M)\) bits per item (because we need to ID each item wrt universe), and \(O\qty(\log M)\) to store the hash function. example of 1/2-wise independence Let’s pick \(k\) strings \(r^{(1)} … r^{(k)} \sim \qty {0,1}^{n}\) uniform random things, and \(k\) bits \(b_{1}, …, b_{k} \sim \qty {0,1}\) uniform random bits. This is \(O\qty(kn)\) bits of randomness. \begin{equation} h\qty(y) = \qty(r^{(1)}y + b_1, r^{(2)} y + b_2, \dots, r^{(k)} y + b_{k}) \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