5
$\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)$.

Improve this question
$\endgroup$
1
  • 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. ♦
    Commented Dec 13, 2014 at 6:00

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ Could you explain what this means? I don't understand. $\endgroup$
    – Chris
    Commented Dec 13, 2014 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
    Commented Dec 13, 2014 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
    Commented Dec 13, 2014 at 10:30

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.