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

1 Answer 1

4
$\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 and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.