4
$\begingroup$

I'm trying to find a family of hash functions mapping $\{1, 2, ..., 2^n\}$ to $\{0, 1\}$ that is 2-wise independent but not 3-wise independent. Any ideas on that?

I know two 2-wise independent families but I think they are 3-wise independent as well:

1) Let x be a vector in $\{0, 1\}^n$. The hash functions are $h_{a, b}(x)=a^\top x+b \mod 2$ for all $a\in\{0, 1\}^n$ and $b\in\{0, 1\}$.

2) Consider $GF(2^n)$. The hash functions are $$h_{a, b}(x)= \text{the last bit of }a \cdot x+b $$ for all $a, b\in GF(2^n)$.

$\endgroup$
  • 1
    $\begingroup$ 1. What families of 2-independent hash functions do you know? Spend a few hours with a few textbooks and review the standard constructions: I think you'll find that many of the standard constructions meet your requirements. 2. Hint: What happens if you generalize your constructions to a field of characteristic larger than 2? $\endgroup$ – D.W. Dec 13 '14 at 6:00
0
$\begingroup$

The smallest example I could find is $$ 0001 \\ 0010 \\ 0100 \\ 1000 \\ 0011 \\ 0101 \\ 0110 \\ 1001 \\ 1010 \\ 1100 \\ 1111 \\ 1111 $$ I'll leave you to generalize this to larger $n$.

$\endgroup$
  • 2
    $\begingroup$ Could you explain what this means? I don't understand. $\endgroup$ – Chris Dec 13 '14 at 4:21
  • $\begingroup$ Actually I think I find one. Similar to 1), the functions are $h_a(x)=a^\top x \mod 2$ for all $a\in\{0,1\}^n$, but $\vec0$ is not in the domain now (so the domain is $\{1,2,\cdots,2^n−1\}$). $\endgroup$ – Chris Dec 13 '14 at 4:50
  • $\begingroup$ I've described a family of 12 hash functions mapping $\{1,2^2\}$ to $\{0,1\}$ which is 2-wise independent but not 3-wise independent (with respect to the uniform measure on the 12 hash functions). $\endgroup$ – Yuval Filmus Dec 13 '14 at 10:30

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.