2
$\begingroup$

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

$\endgroup$

1 Answer 1

3
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.