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.

  • $\begingroup$ Try to use the definition of 3-wise independence. Using the definition is always a good idea. $\endgroup$ – Yuval Filmus Nov 11 '18 at 23:29
  • $\begingroup$ The notation $\mathbb{Z}_q$ that you use is highly nonstandard; usually $\mathbb{Z}_q$ is the cyclic group of $q$ elements. $\endgroup$ – Yuval Filmus Nov 11 '18 at 23:31
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Nov 11 '18 at 23:32
  • $\begingroup$ 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. $\endgroup$ – 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\}. $$

This is a property that you can prove using linear algebra.


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.