2
$\begingroup$

I've been given the following two families of hash functions:

H

and

G

enter image description here

Each family has three functions $\{0,1,2,3,4\} \to \{0,1,2\}$ that can be seen in the tables above. For each family I need to decide whether it's universal. I know that a family of hash functions $F$ is called universal if for every $x \neq y$, $\text{Pr}(f(x) = f(y)) \le \frac{1}{m}$ ($f$ is a function in $F$). However, I don't understand how to calculate this probability. Should I calculate it for any one of the functions or for the whole family?

$\endgroup$
2
$\begingroup$

As you have stated, given a family $H$ of hash functions, the condition for universality is $\forall x,y, x \neq y: \text{P}_{h \in H}(h(x) \neq h(y)) \le \frac{1}{m}$. The probability is taken over $h \in H$, which is picked following a uniform distribution.

If you think for a while about what that means, you'll realize you need simply check whether there is at most one collision (i.e., equal entries) for any two distinct columns (i.e., every pair of $x$ and $y$) in the respective family's table. Hence, $G$ is universal, but $H$ is not; I'll let you figure out why.

$\endgroup$
  • $\begingroup$ I think i understand now. I think the thing that confused me the most was over what the probability is taken and you've explained it. Thanks! $\endgroup$ – marianov May 6 at 13:30

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.