0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

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

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.