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?


1 Answer 1


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.

  • $\begingroup$ Thanks! It is really simple $\endgroup$ Commented Dec 4, 2019 at 10:16

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.