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

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?

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.
• Oh sorry. I meant $|U|$ to be larger than $m$? Let me fix that. – Anush Feb 14 '19 at 17:07