# 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?

## 1 Answer

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 at 17:07
• Is there anything else you forgot about the question? I don't like continuously changing my answer to fit an ever-changing question. – Yuval Filmus Feb 14 at 17:12
• No I don’t think so. Thank you for your very nice answer to the first version. – Anush Feb 14 at 17:13
• Well, it makes a nice exercise. – Yuval Filmus Feb 14 at 17:24
• 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. – Yuval Filmus Feb 14 at 18:58