## Exercises 22. 4. 2021: Hash functions

$$\def\H{\mathcal{H}} \def\U{\mathcal{U}} \def\B{\mathcal{B}} \def\L{\mathcal{L}}$$

#### 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.