# Prove hash family is 3-wise independent

Let $$q$$ be a prime number and let $$\mathbb{Z}_q = \left\{1,\dots,q-1\right\}$$; I need to prove that the family $$\mathcal{H} = \left\{h_s \colon \mathbb{Z}_q \rightarrow \mathbb{Z}_q\right\}_{s \in \mathbb{Z}_q^3}$$ is 3-wise independent, where $$h_s$$ is defined as:

$$h_s(x):=h_{s_0,s_1,s_2}(x):=s_0 + s_1 x + s_2 x^2 \bmod q$$

How could I do it? My intuition would be proving that it is 1-wise independent and use the property $$x_1,\dots,x_t \in \mathcal{X}, \quad y_1,\dots,y_t \in \mathcal{Y}, \quad \Pr[h_s(x_1)=y_1 \wedge \dots\wedge h_s(x_t)=y_t \mid s \leftarrow _\ \mathcal{S}]=\frac{1}{|\mathcal{Y}|^t},$$ but I'm not sure how to do that.

• Try to use the definition of 3-wise independence. Using the definition is always a good idea. – Yuval Filmus Nov 11 '18 at 23:29
• The notation $\mathbb{Z}_q$ that you use is highly nonstandard; usually $\mathbb{Z}_q$ is the cyclic group of $q$ elements. – Yuval Filmus Nov 11 '18 at 23:31
• Indeed, there is no guarantee that the image of your function actually lies in $\mathbb{Z}_q$. You probably meant the field $\mathbb{F}_q$ with $q$ elements. – Yuval Filmus Nov 11 '18 at 23:32
• Note that being 3-wise independent is stronger than being 1-wise independent. For example, you family is 3-wise but not 4-wise independent. – Yuval Filmus Nov 11 '18 at 23:34

Let's assume that $$\mathbb{Z}_q$$ is the field of size $$q$$. In order for your family to be 3-wise independent, we need the following condition to hold: for every $$x_1,x_2,x_3,y_1,y_2,y_3 \in \mathbb{Z}_q$$ where the $$x_i$$ are all different, $$\Pr_s[h_s(x_1) = y_1 \land h_s(x_2) = y_2 \land h_s(x_3) = y_3] = \frac{1}{q^3}.$$ Since your family consists of $$q^3$$ functions, this is the same as the following property:
If $$x_1,x_2,x_3 \in \mathbb{Z}_q$$ are all different, then for every $$y_1,y_2,y_3 \in \mathbb{Z}_q$$ there exist unique $$s_0,s_1,s_2 \in \mathbb{Z}_q$$ such that $$s_0 + s_1 x_i + s_2 x_i^2 = y_i, \quad i \in \{1,2,3\}.$$