2
$\begingroup$

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.

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

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

$\endgroup$
  • $\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 '14 at 2:53
  • $\begingroup$ Also, what makes you think that the family is 3-wise independent? $\endgroup$ – Kelsey Dec 2 '14 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$ – Yuval Filmus Dec 2 '14 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 '14 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$ – Yuval Filmus Dec 2 '14 at 4:55

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.