5
$\begingroup$

A family of hash functions $H_w$ is said to be weakly universal if for all $x \ne y$ :

$$P_{h \in H_w}(h(x) = h(y)) \leq 1/m$$

Here the function $h:U \rightarrow [m]$ is chosen uniformly from the family $H$ and we assume $|U| > m$.

A family of hash functions $H_s$ is said to be strongly universal if for all $x \ne y$ and $k, \ell \in [m]$:

$$P_{h \in H_s}(h(x) = k \land h(y) = \ell) = 1/m^2$$

What is a concrete example of a hash function family which is weakly universal but not strongly universal?

$\endgroup$

1 Answer 1

5
$\begingroup$

Let $U = [m]$, and let $h$ be the identity function.

If you insist that $|U| > m$, then you can take $U = [m+1]$, and consider the functions $h_i$, for $i \in [m]$, given by $$ h_i(x) = \begin{cases} x & \text{if } x \neq m+1, \\ i & \text{if } x = m+1. \end{cases} $$ The same approach can be used for arbitrary $|U|$: fix the first $m$ coordinates, and make all other coordinates uniformly and independently random.

$\endgroup$
8
  • $\begingroup$ Oh sorry. I meant $|U|$ to be larger than $m$? Let me fix that. $\endgroup$
    – Simd
    Feb 14, 2019 at 17:07
  • 2
    $\begingroup$ Is there anything else you forgot about the question? I don't like continuously changing my answer to fit an ever-changing question. $\endgroup$ Feb 14, 2019 at 17:12
  • $\begingroup$ No I don’t think so. Thank you for your very nice answer to the first version. $\endgroup$
    – Simd
    Feb 14, 2019 at 17:13
  • 1
    $\begingroup$ Well, it makes a nice exercise. $\endgroup$ Feb 14, 2019 at 17:24
  • 1
    $\begingroup$ I don’t see any lookup tables in your question. Perhaps you need to spend more time formulating your question. When you have a concrete follow-up question, you can ask it separately. $\endgroup$ Feb 14, 2019 at 18:58

Your Answer

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

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