1
$\begingroup$

Most definitions of a $k$-wise independent family of hash functions I have encountered state that a family $H$ of hash functions from $D$ to $R$ is k-wise independent if for all distinct $x_1, x_2,\dots, x_k \in D$ and $y_1, y_2,\dots, y_k \in R$,

$$\mathbb{P}_{h \in H}(h(x_1) = y_1, h(x_2) = y_2, \dots, h(x_k) = y_k) = \frac{1}{|R|^k}$$

The Wikipedia article on k-wise independent hash functions (which uses the above definition) claims that the definition is equivalent to the following two conditions:

(i) For all $x \in D$, $h(x)$ is uniformly distributed in $R$ given that $h$ is randomly chosen from $H$.

(ii) For any fixed distinct keys $x_1, x_2,\dots, x_k \in D$, as $h$ is randomly drawn from $H$, the hash codes $h(x_1), h(x_2), \dots, h(x_k)$ are independent random variables.

It is not obvious to me how one proves (i) from the above definition without explicitly assuming (ii) in the definition as well (and vice-versa). How is the definition sufficient for proving both (i) and (ii)?

$\endgroup$
1
$\begingroup$

Throughout, we assume that $|D| \geq k$.

Suppose that $H$ satisfies, for all distinct $x_1,\dots,x_k \in D$ and all $y_1,\ldots,y_k \in R$, $$ \Pr_{h \in H}[h(x_1)=y_1,\ldots,h(x_k)=y_k] = \frac{1}{|R|^k}. $$ Now let $x \in D$ be arbitrary. Since $|D| \geq k$, we can find $x_2,\ldots,x_k \in D$ such that $x,x_2,\ldots,x_k$ are distinct. For each $y \in R$, $$ \Pr_{h \in H}[h(x)=y] = \sum_{y_2,\ldots,y_k \in R} \Pr_{h \in H}[h(x)=y,h(x_2)=y_2,\ldots,h(x_k)=y_k] = \\ \sum_{y_2,\ldots,y_k \in R} \frac{1}{|R|^k} = \frac{|R|^{k-1}}{|R|^k} = \frac{1}{|R|}. $$ This proves (i). To see (ii), let $x_1,\ldots,x_k \in D$ be distinct. Then for all $y_1,\ldots,y_k$, $$ \Pr_{h \in H}[h(x_1)=y_1,\ldots,h(x_k)=y_k] = \frac{1}{|R|^k} = \prod_{i=1}^k \frac{1}{|R|} = \prod_{i=1}^k \Pr_{h \in H}[h(x_i) = y_i]. $$

In the other direction, suppose that (i) and (ii) hold. Then for all distinct $x_1,\ldots,x_k \in D$ and $y_1,\ldots,y_k \in R$, $$ \Pr_{h \in H}[h(x_1)=y_1,\ldots,h(x_k)=y_k] = \prod_{i=1}^k \Pr_{h \in H}[h(x_i) = y_i] = \prod_{i=1}^k \frac{1}{|R|} = \frac{1}{|R|^k} . $$

$\endgroup$
2
  • $\begingroup$ Nice, many thanks! How did it occur to you to view the event ${h(x) = y}$ as the union of events $\{h(x) = y, h(x_2) = y_2, ..., h(x_k) = y_k\}$ for all $(y_2, ..., y_k) \in R^{k-1}$? While I can understand and appreciate your proof, I'm concerned something crucial in my understanding of basic probability theory is missing for me to have this kind of intuition for such problems. $\endgroup$
    – kotu
    Feb 16 at 22:45
  • 1
    $\begingroup$ It’s very standard. Once you’ve seen it a few times, it becomes second nature. $\endgroup$ Feb 16 at 23:06

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.