How to show independence and uniform distribution of hash codes from k-wise independent hash functions?

Question

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

Answer 1

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