3
$\begingroup$

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

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.

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

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.

$\endgroup$

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.