[Solved]: Show that the following family of hash functions is $2$-wise independent but not $3$-wise independent

Problem Detail: 

I've really been thinking about and working on this problem for a while, and I would appreciate if someone could offer any help towards the solution.

Consider the following family of hash functions that map $w$-bit numbers to $l$-bit numbers (i.e. the range is $\{0,...,m-1\}$ where $m=2^l$):

$\mathcal{H} = \{h_{A,b}|A\in \{0,1\}^{l\times w}, b \in \{0,1\}^{l\times 1}\}$, where $h_{A,b}(x) = Ax+b\mod 2$

Show that $\mathcal{H}$ is $2$-wise independent but not $3$-wise independent ($\mathcal{H}$ is $k$-wise independent if for any $k$ inputs $x_1,...,x_k$ and hash values $v_1,...,v_k$, $\Pr\limits_{h\in\mathcal{H}} \left( \bigwedge\limits_{1\le i\le k} h(x_i)=v_i \right)=m^{-k} $).

I'm first trying to show that $\mathcal{H}$ is $2$-wise independent. So consider any two inputs $x_1, x_2$ and hash values $v_1,v_2$. Then it's required that $\Pr \left( h(x_1)=v_1 \wedge h(x_2)=v_2 \right)=\frac{1}{m^2}$.

$$\Pr \left( h(x_1)=v_1 \wedge h(x_2)=v_2\right)$$

$$\Rightarrow \Pr\left( Ax_1+b = v_1 \mod 2\wedge Ax_2+b=v_2 \mod 2\right)$$

What about this equation shows that the probability is $\frac{1}{m^2}$? If we were trying to show $3$-wise independence, we would have:

$$\Pr\left( Ax_1+b = v_1 \mod 2 \wedge Ax_2+b=v_2 \mod 2 \wedge Ax_3+b=v_3 \mod 2\right)$$

Why is this not $\frac{1}{m^3}$?

I just don't know how to evaluate an expression like $\Pr\left( Ax_1+b = v_1 \mod 2 \wedge Ax_2+b=v_2 \mod 2 \wedge Ax_3+b=v_3 \mod 2\right)$. I've tried searching online for similar problems, but none seem to help with solving this one specifically.

Asked By : Kelsey

Answered By : Yuval Filmus

Hint for showing 2-wise independence: Given $x_1,x_2$ and $v_1,v_2$, write the desired equations in a different way: $$ b = v_1 - Ax_1, \\ A(x_2-x_1) = v_2 - v_1. $$

Regarding 3-wise independence: I could be missing something, but it seems that the family is 3-wise independent.

Hint for refuting 4-wise independence: Take $x_3 = x_1 + x_2$ and $x_4 = 0$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33705

3.2K people like this

 Download Related Notes/Documents