1
$\begingroup$

Consider the hash function mapping $w$-bit keys to hash values in $\{0,...,m-1\}$. Suppose $w=cr$. Interpret a $w$-bit key $x$ as a vector $(x_1,...,x_c)$ of $c$ $r$-bit keys.

Consider the hash family:

$$H = \{h_{T_1,...,T_c}:T_i \in \{0,...,m-1\}^{2^r}\}$$

where

$$h_{T_1,...,T_c}(x) = \sum\limits_{1\le i \le c}T_i[x_i]\mod m$$

Prove that $H$ is $3$-wise independent, but not $4$-wise independent.

$H$ is $k$-wise independent if for inputs $x_1,...,x_k$ and output $v_1,...,v_k$, $\Pr[h(x_1) = v_1 \wedge ... \wedge h(x_k)=v_k] = \frac{1}{m^k}$

So I can certainly see why $H$ is $1$-wise and $2$-wise independent if we're choosing inputs to the hash function that must be different from each other. However, I'm having a lot of trouble seeing why the family is not $4$-wise independent, which I think lends greatly to my difficulty in proving that the family is $3$-wise independent.

So for the family to not be $4$-wise independent, if we have inputs $x_1,...,x_4$ and outputs $v_1,...,v_4$, $\Pr[h(x_1)=v_1\wedge...\wedge h(x_4)=v_4]\not = \frac{1}{m^4}$. I am trying to think of a counterexample where this will not be the case, but it seems like we need, for example, $x_4$ to be constructed in such a way that $v_4$ can be attained by some combination of $v_1,v_2,v_3$. However, all of $x_1,...,x_4$ are $w$-bit keys, so even if $x_4$ had bits taken from each of $x_1,x_2,x_3$, the output $v_4$ would still be some random sum corresponding to the $c$ $r$-bit blocks accessing each $T_i$.

Is there something I'm missing here? Perhaps it's not possible for $v_4$ to be some combination of $v_1,...,v_3$, but how else would we show that $H$ is not $4$-wise independent?

$\endgroup$
  • $\begingroup$ @YuvalFilmus your assistance would be appreciated if you have the time! $\endgroup$ – Kelsey Dec 3 '14 at 23:06
0
$\begingroup$

Hint for refuting 4-wise independence: Suppose for simplicity that $c = 2$, pick some $\alpha \neq \beta$ of length $r$, and consider the four inputs $(\alpha,\alpha),(\alpha,\beta),(\beta,\alpha),(\beta,\beta)$.

Hint for proving 3-wise independence: Let the three inputs be $x,y,z$. If there is some coordinate $i$ such that $x_i,y_i,z_i$ are all different then we are done. Otherwise, without loss of generality there are coordinates $i,j$ such that $x_i = y_i \neq z_i$ and $x_j = z_j \neq y_j$, and we are again done.

$\endgroup$
  • $\begingroup$ What does the input $(\alpha,\alpha)$ mean? $\endgroup$ – Kelsey Dec 3 '14 at 23:47
  • $\begingroup$ Yes, that's according to your notation $x = (x_1,\ldots,x_c)$. $\endgroup$ – Yuval Filmus Dec 3 '14 at 23:49
  • $\begingroup$ I still don't understand how you come up with these so quickly. Teach me your ways! Also, what more is there to proving (non) $3$-wise independence (i.e. why is this a hint rather than a formal proof)? $\endgroup$ – Kelsey Dec 4 '14 at 9:01
  • $\begingroup$ It's very close to a proof, but still not written out in full. $\endgroup$ – Yuval Filmus Dec 4 '14 at 15:29
  • $\begingroup$ I'm assuming a full proof would just require a more elaborate explanation. Is this true? $\endgroup$ – Kelsey Dec 4 '14 at 16:08

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.