snippetMinor
What is an example of a weakly universal hash function that is not pairwise independent?
Viewed 0 times
whatindependentuniversalexampleweaklyfunctionhashthatpairwisenot
Problem
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?
$$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?
Solution
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.
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.
Context
StackExchange Computer Science Q#104361, answer score: 5
Revisions (0)
No revisions yet.