Let $f$, $g$, and $h$ be hash functions that each map binary strings of length $2n$ to binary strings of length $n$. Suppose that $h(x) = f(g(x)||g(x))$. Prove that if $f$ and $g$ are collision resistant then $h$ is also collision resistant.

This question was asked on an earlier assignment and my professor had taken it up in class using proof by contrapositive. I am expecting a question like this to show up on our final but I have forgotten how he answered it. Could anyone off some insight into how I can answer this?

  • $\begingroup$ If you just write out the contrapositive statement you are pretty much there. $\endgroup$
    – otus
    Nov 17 '15 at 16:20
  • $\begingroup$ That is, "suppose $h$ is not collision resistant; that is, we knew of a collision in $h$, two values $x \ne x'$ where $h(x) = h(x')$. What does that imply about $f$ or $g$?" $\endgroup$
    – poncho
    Nov 17 '15 at 16:54
  • $\begingroup$ Next step is making two cases, according to if $g(x)=g(x')$, or not. $\endgroup$
    – fgrieu
    Nov 17 '15 at 21:21

Recall that randomly chosen functions, used to model good hash functions, are collision resistant if we need on the order of $2^{n/2}$ queries in order to discover a collision with success probability a constant bounded away from zero.

Proof by contrapositive:

Assume $h$ is NOT collision resistant. Then we can find such collisions much faster than specified above, i.e., we can find $x\neq x'$ $x,x' \in \{0,1\}^{2n}$ with $h(x)=h(x')$. There are two possibilites.

In the first case $g(x)=g(x')$, in which case any function $f$ would yield a collision in $h$.

If on the other hand, $g$ is collision resistant and thus $g(x)\neq g(x')$, we must now have $f(g(x) || g(x)) = f(g(x') || g(x'))$ which implies that $f$ is not collision resistant since it is giving a collision to distinct inputs.


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.