# Two definitions of universal hash functions

I have seen two definitions of universal hash functions in the literature.

For any $i \geqslant 2$ let $[i]=\{1,\ldots,i\}$.

Definition 1:

A family $\mathcal H$ of hash functions from $[n]$ to $[m]$ is a $k$-universal family of hash functions if for any distinct $x_1,\ldots,x_k\in[n]$ and any possibly identical $v_1,\ldots,v_k\in[m]$, $$\Pr\limits_{h\in\mathcal H} [h(x_1)=v_1\wedge \cdots \wedge h(x_k) = v_k] \leqslant 1/m^k \enspace .$$

Definition 2:

A family $\mathcal H$ of hash functions from $[n]$ to $[m]$ is a $k$-universal family of hash functions if for any distinct $x_1,\ldots,x_k\in[n]$, $$\Pr\limits_{h\in\mathcal H} [h(x_1)=\cdots=h(x_k) ] \leqslant 1/m^{k-1} \enspace .$$

In both definitions if equality holds then it is called strongly $k$-universal or alternatively $k$-wise independent hash family.

Clearly the first definition implies the second. But is the other direction true?

It is easy to see that this is not the case for $n\leqslant m$.

This is a counter example when $[n]\subseteq [m]$:

Consider the family $\mathcal H$ composed of only one element, the identity function: $x \mapsto x$. It satisfies the second definition since for all $x \neq y \in [n], \Pr_{h\in\mathcal H} [h(x) = h(y)] = 0 \leqslant 1/m^{k-1}$. However, it does not satisfy the first definition since for all $x,y\in[n], \Pr_{h\in\mathcal H}[h(x) = x \wedge h(y) = y] = 1 > 1/m^k$.

This answer is inspired by this other answer.

However, hash functions are usually employed in applications where $n>m$. So my question is whether this is also the case for $n>m$.

## 1 Answer

The two definitions are not equivalent. The second definition does not imply the first. You can take $\mathcal{H}$ to be the collection of all functions $h$ such that $h(1) = 1$.