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$ – Squeamish Ossifrage May 14 '18 at 13:44
  • $\begingroup$ With $\epsilon$-almost universal I mean that $Pr[f(x)=g(x)]<\epsilon$ $\endgroup$ – Digimon Kaiser May 15 '18 at 8:30
  • $\begingroup$ And yes, you are right, I fixed it above ;) $\endgroup$ – Digimon Kaiser May 15 '18 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$ – Squeamish Ossifrage May 15 '18 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$ – Digimon Kaiser May 16 '18 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')$.)


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.