I'm trying to solve the following problem:

Given two CRHF $H_1:2^{4n}\to2^{2n}$, $H_2:2^{2n}\to 2^n$, construct the following hash function $H^{*}=H_2(H_1(x))$ compressing from $2^{4n}\to 2^n$.

We want to demonstrate that if $H_1$ and $H_2$ are collision resistant then $H^*$ must be collision resistant too.

I made the following reduction


However I'm still unsure on how to calculate ”BAD event” in which $A^{H^∗}$ outputs a collision for $H_{s_1}$, in this case $x^∗=x′$ and the second part of the reduction doesn’t work.

  • $\begingroup$ Sure, I don't have it handy right now. I will post my solution as soon as possible. Thanks! $\endgroup$
    – blazef104
    Commented Dec 11, 2018 at 20:20
  • 1
    $\begingroup$ If $H_1$ and $H_2$ are collision resistant, then $H^*$ should be; if you demonstrate a collision in $H^*$, then you have a collision in either $H_1$ or $H_2$ (hence demonstrating that $H_1$ or $H_2$ wasn't collision resistant after all) $\endgroup$
    – poncho
    Commented Dec 12, 2018 at 15:27
  • $\begingroup$ @poncho I had the same idea in the beginning but I was trying to make a straightforward demonstration. However now I am seriously thinking of making a reduction like you said. Thanks! $\endgroup$
    – blazef104
    Commented Dec 12, 2018 at 15:48
  • $\begingroup$ @kelalaka yeah and the more I tried to put my demonstration in a formally correct way the more It looked incorrect. Anyway thank you both guys ;) $\endgroup$
    – blazef104
    Commented Dec 13, 2018 at 21:49
  • $\begingroup$ @kelalaka I've edited my post with one of my ideas $\endgroup$
    – blazef104
    Commented Dec 15, 2018 at 15:40

1 Answer 1


Assume that, $H_1 \text{ and } H_2$ are collision resistant and $H^*$ is not. We will show that one of the $H_1 \text{ and } H_2$ can not be a collision resistant.

Let $x_1 \neq x_2$ be inputs such that $$H^*(x_1) = H^*(x_2).$$ $$H_2(H_1(x_1)) = H_2(H_1(x_2)).$$i.e we have a collision pair.

Now, if $H_1$ is collision resistant then $$y_1 = H_1(x_1) \neq H_1(x_2) = y_2 .$$

Note : The equality holds only with negligible probability, then $H_2(H_1(x_1)) = H_2(H_1(x_2))$ is a collision with a negligible probability.

Now, $H_2(y_1) = H_2(y_2)$ since $H^*$ is not collision resistant. But we found a collision for $H_2$ given a collision for $H^*$. This is a contradiction since $H_2$ is collision resistant therefore this implies that $H^*$ is collision resistant, too.


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.