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

Question

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.

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.