# Does Composition of compressing Collision Resistant Hash Functions $H^{*}=H_2(H_1(x))$ is Collision Resistant?

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.

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.

• Sure, I don't have it handy right now. I will post my solution as soon as possible. Thanks! – blazef104 Dec 11 '18 at 20:20
• 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) – poncho Dec 12 '18 at 15:27
• @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! – blazef104 Dec 12 '18 at 15:48
• @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 ;) – blazef104 Dec 13 '18 at 21:49
• @kelalaka I've edited my post with one of my ideas – blazef104 Dec 15 '18 at 15:40

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.