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

- Recall the definition of c-universality and (k,c)-independence.
- 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?
- 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.
- 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]\}\).

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