What is an example of a weakly universal hash function that is not pairwise independent?

Question

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?

Answer 1

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.