# Combining two almost universal hash functions

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?

• 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.) May 14, 2018 at 13:44
• With $\epsilon$-almost universal I mean that $Pr[f(x)=g(x)]<\epsilon$ May 15, 2018 at 8:30
• And yes, you are right, I fixed it above ;) May 15, 2018 at 8:32
• 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. May 15, 2018 at 13:39
• 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$ May 16, 2018 at 12:44

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')$.)