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.

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

1 Answer 1


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

  • $\begingroup$ 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}$? $\endgroup$
    – Kelsey
    Dec 2, 2014 at 2:53
  • $\begingroup$ Also, what makes you think that the family is 3-wise independent? $\endgroup$
    – Kelsey
    Dec 2, 2014 at 2:53
  • $\begingroup$ @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. $\endgroup$ Dec 2, 2014 at 3:00
  • $\begingroup$ 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? $\endgroup$
    – Kelsey
    Dec 2, 2014 at 4:53
  • $\begingroup$ @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]$. $\endgroup$ Dec 2, 2014 at 4:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.