Exercises 22. 4. 2021: Hash functions

Notation:

• \(\U\) : universe
• \(U = |\U|\)
• \(\B\) : buckets
• \(m = |\B|\)

Ex. 1: Universality and independence

1. Recall the definition of c-universality and (k,c)-independence.
2. Consider a family \(\mathcal{H}_1 = \{h(x) = x\}\) that contains a single hash function \(h(x) = x\) (that is, \(\B = \U\). Is family \(\H_1\) c-universal for some c? Is it (k,c)-independent for some k and c?
3. Show that family \(\H_2 = \{h_a(x) = a | a\in\B\}\) of all constant functions is (1,1)-independent. Also show \(\H_2\) is not (2,c)-independent nor c-universal for any c.
4. Prove the following claim from the lecture
   • \(\H\) is (k,c)-independent \(\Rightarrow\) \(\H\) is (k-1,c)-independent (\(k > 1\))
   • \(\H\) is (2,c)-independent \(\Rightarrow\) \(\H\) is c-universal

Ex. 2 Linear functions

Recall we have defined function \(h_{a,b}(x) = ((ax + b) \bmod p) \bmod m\) for any \(a,b \in [p]\), where \(p\) is a prime number and \(\U = [p]\).

We define a family of linear functions \(\L = \{h_{a,b}\,|\, a,b\in [p]\}\) and a family \(\L' = \L\setminus \{h_{0,b}\,|\,b\in [p]\}\).

1. We know from the lecture that \(\L\) is 2-independent. Prove that \(\L\) is not 3-independent. Hint: Consider only case with \(m = p\). Use the fact that system of two linear equations with two variables has a unique solution (unless you choose bad parameters, of course).
2. Prove that \(\L'\) is 2-independent. Hint: We can use similar argument as in the proof for \(\L\) from the lecture. The main issue is that the events are now not independent as we require \(s \neq r\) (i.e. we condition the probablity with this). But we can circumvent this problem by using the law of total probability.