Skip to main content
added 4 characters in body
Source Link
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

Most definitions of a k$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... x_k \in D$$x_1, x_2,\dots, x_k \in D$ and $y_1, y_2 ... y_k \in R$$y_1, y_2,\dots, y_k \in R$,

$$\mathbb{P}_{h \in H}(h(x_1) = y_1, h(x_2) = y_2, ..., h(x_k) = y_k) = \frac{1}{|R|^k}$$$$\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... x_k \in D$$x_1, x_2,\dots, x_k \in D$, as h$h$ is randomly drawn from $H$, the hash codes $h(x_1), h(x_2), ..., h(x_k)$$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)?

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... x_k \in D$ and $y_1, y_2 ... y_k \in R$,

$$\mathbb{P}_{h \in H}(h(x_1) = y_1, h(x_2) = y_2, ..., 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... x_k \in D$, as h is randomly drawn from $H$, the hash codes $h(x_1), h(x_2), ..., 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)?

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

Source Link
Johnny
  • 363
  • 1
  • 12

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

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... x_k \in D$ and $y_1, y_2 ... y_k \in R$,

$$\mathbb{P}_{h \in H}(h(x_1) = y_1, h(x_2) = y_2, ..., 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... x_k \in D$, as h is randomly drawn from $H$, the hash codes $h(x_1), h(x_2), ..., 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)?