6
$\begingroup$

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$.

$\endgroup$
4
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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