# Pairwise hash functions that are independent from each other

Is there there a way to build a collection of universal hash functions $$H=\{h| h:U\to D \}$$ where the values of two hash functions are independent one from another? i.e., $$\Pr_{h_1,h_2\in H}(h_1(x)=y \land h_2(z)=w )=|D|^{-2}$$ for each $$x,y,z,w\in U$$.

Also, is there a term for such collection?

If you select $$h_1,h_2$$ independently at random, then by definition

$$\Pr_{h_1,h_2}[h_1(x)=y \land h_2(z)=w] = \Pr_{h_1}[h_1(x)=y] \times \Pr_{h_2}[h_2(z)=w].$$

If your hash family is universal, then both probabilities on the right-hand side will be $$1/|D|$$.

In other words, if $$H$$ is universal, then it automatically follows that

$$\Pr_{h_1,h_2}[h_1(x)=y \land h_2(z)=w] = 1/|D|^2.$$

Every universal collection works -- no extra conditions or requirements are needed.

• Thanks! It is really simple – user3563894 Dec 4 '19 at 10:16