We say that a set of functions $S$ is $\epsilon$-almost-universal if for any function $f \in S$, it holds that $\Pr[f(m) = f(m')] < \epsilon$ for $m \not = m'$.

Assume that we have the following two sets of hash functions:

$F = \{f:M \rightarrow X\}$, which is $\epsilon_1$-almost-universal.
$G = \{g:X \rightarrow Y \}$, which is $\epsilon_2$-almost-universal.

Then, there exists a third set of hash functions $H$ for that it holds:
$H=\{h:M \rightarrow Y\}$ where $h(M)=g(f(M))$ and $H$ is $(\epsilon_1 + \epsilon_2)$-almost-universal.

Now my question is: Why is this the case? Why is $H$ $(\epsilon_1 + \epsilon_2)$-almost-universal?

  • 3
    $\begingroup$ Can you start by defining what $\epsilon$-almost universal means, and show what work you've tried so far? (Also: Do you mean $g\colon X \to Y$? Otherwise the domains and codomains don't match up.) $\endgroup$ May 14, 2018 at 13:44
  • $\begingroup$ With $\epsilon$-almost universal I mean that $Pr[f(x)=g(x)]<\epsilon$ $\endgroup$ May 15, 2018 at 8:30
  • $\begingroup$ And yes, you are right, I fixed it above ;) $\endgroup$ May 15, 2018 at 8:32
  • $\begingroup$ Do you mean $\Pr[f(m) = f(m')] < \epsilon$ for $m \ne m'$? $f$ and $g$ have different domains and codomains, so $f(x) = g(x)$ doesn't make sense. Suppose $h(m) = h(m')$; what can you conclude from that? There are two possible collisions that it might imply—expand it out by the laws of probability theory. $\endgroup$ May 15, 2018 at 13:39
  • $\begingroup$ Oh, you are right, I missunderstood the topic. It's $Pr[f(x)=f(x')]<\epsilon_1$ and $Pr[g(x)=g(x')]<\epsilon_2$ $\endgroup$ May 16, 2018 at 12:44

1 Answer 1


Under what circumstances is $g(f(m)) = g(f(m'))$ for any $m \ne m'$? With what probability do these circumstances happen?

(Hint: Write $x = f(m)$ and $x' = f(m')$ and consider the probability of $g(x) = g(x')$.)


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.