# How to find a 2-wise independent hash family that is not 3-wise independent?

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

• 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? – D.W. Dec 13 '14 at 6:00

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$.
• 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\}$). – Chris Dec 13 '14 at 4:50
• 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). – Yuval Filmus Dec 13 '14 at 10:30