Why is double hashing universal hash function still a universal hash function?

Question

Here is the definition of universal hash function for $h \in H$ (family of universal hash function)

$$\forall x, y \in U x \neq y : Pr_{h \in H}[h(x) = h(y)] \leq \frac{1}{m}$$

Double hashing is the following

$$h_a , h_b \in H$$

$$h_i(x, m) = (h_a(x) + i \times h_b(x)) \mod m $$

Is there a proof that shows that double hashing two universal functions with arbitrary $i$ will produce another universal function?

If

$$ k = (h_a(x) + h_b(x))$$

Can't we say that there is $k + 1$ more ways of collision?

$$ 5 = 0 + 5, 1 + 4, 2 + 3, 3 + 2, 4 + 1, 5 + 0 $$

Answer 1

Is there a proof that shows that double hashing two universal functions with arbitrary $i$ will produce another universal function?

If $i$ is fixed, then no, $h_i$ need not be universal.

For a simple counterexample, consider $U$ which consists of 2 elements and $H$ which consists of 1 element $h$, with $\alpha$ and $\beta$, with $h(\alpha) = 0$ and $h(\beta) = 1$. It is easy to see that $H$ is universal.

However, if we select $i = m-1$, then $h_i(x, m)$ is not universal (as it is 0 for both possible inputs $x$).

Now, let us consider where $i$ is uniformly distributed; that is, the family $H'$ that $h_i(x, m)$ belongs to contains all $i$ values.

Then, if $m$ is composite, the answer is still no. Similar counterexample: suppose $a$ is a proper factor of $m$; then, consider the $H$ which consists of 1 element $h$, with $h(\alpha) = 0$ and $h(\beta) = a$

Then, $h_i(\alpha, m) = h_i(\beta, m)$ with probability $a/m$; not universal.

On the other hand, if $m$ is prime, then $h_i$ will necessarily be universal (and we need not assume that the $h_b$ side is universal); this can be shown for any two distinct inputs $\alpha, \beta$ with a simple case analysis (where the probability in both those cases is $\le 1/m$):

• If $h_b(\alpha) = h_b(\beta)$, then the probability is $\le 1/m$ (because of the universality of $h_a$)

• If $h_b(\alpha) \ne h_b(\beta)$, then there is a unique value $i$ with $h_a(\alpha) + i h_b(\alpha) = h_a(\beta) + i h_b(\beta) \mod m$, and as there are $m$ possible values of $i$, $i$ will be that unique value with probability $1/m$