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

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.

• Can you show that the family is 1-wise independent? That would be a good start. Dec 2, 2014 at 0:16

1 Answer

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

• Thank you for an answer. I'm slightly confused though. For 2-wise independence, how does the fact that $A(x_2-x_1)=v_2-v_1$ help in determining the probability? Are we asking $\Pr[A(x_2-x_1)=v_2-v_1]$ now? If so, why is this equal to $\frac{1}{m^2}$? Dec 2, 2014 at 2:53
• Also, what makes you think that the family is 3-wise independent? Dec 2, 2014 at 2:53
• @Kelsey I'm giving hints, not providing a complete solution. For 2-wise independence, I suggest you focus on the special case $x_1 = 0$ and $x_2 = [1\;0\;\cdots\;0]$. Once you understand 2-wise independence, you can perhaps think about 3-wise independence. Dec 2, 2014 at 3:00
• So if $x_1 = \vec{0}$ and $x_2 = [1 0 ... 0]^T$, then we'd have $\Pr[b = v_1 \wedge a_1+b = v_2]$, where $a_1$ is the first column of $A$. I think my trouble is with evaluating these probabilities, in the case of $\Pr[b = v_1 \wedge a_1+b = v_2]$, how can we determine what this probability will equal? Dec 2, 2014 at 4:53
• @Kelsey Right, you have to figure out what this probability is. But you'll have to do it on your own. Try to use the chain rule: $\Pr[b=v_1 \land a_1+b=v_2] = \Pr[b=v_1] \cdot \Pr[a_1=v_2-b|b=v_1]$. Dec 2, 2014 at 4:55