压缩抗碰撞散列函数$H^{*}=H_2(H_1(x))$的组合是否具有抗碰撞能力？

Question

我试图解决以下问题：

给定两个CRHF H_1:2^{4n}\to2^{2n}，H_2:2^{2n}\to 2^n，构造以下从2^{4n}\to 2^n压缩的哈希函数H^{*}=H_2(H_1(x))。我们要证明，如果H_1和H_2具有抗碰撞能力，那么H^*也必须具有抗碰撞能力。

我做了以下的缩减

但是，我仍然不确定如何计算A^{H^∗}输出H_{s_1}冲突的“坏事件”，在本例中，x^∗=x′和还原的第二部分不起作用。

Answer 1

假设H_1 \text{ and } H_2具有抗碰撞能力，而H^*则没有。我们将证明其中一种H_1 \text{ and } H_2不能具有抗碰撞能力。

设x_1 \neq x_2是输入，H^*(x_1) = H^*(x_2).，H_2(H_1(x_1)) = H_2(H_1(x_2)).，即，我们有一个碰撞对。

现在，如果H_1是抗碰撞的，那么y_1 = H_1(x_1) \neq H_1(x_2) = y_2 .

注意:等式只适用于可忽略不计的概率，那么H_2(H_1(x_1)) = H_2(H_1(x_2))是与可忽略概率的碰撞。

现在，H_2(y_1) = H_2(y_2)，因为H^*没有碰撞抗性。但是我们发现了H_2的碰撞和H^*的碰撞。这是一个矛盾，因为H_2是抗碰撞的，因此这意味着H^*也是抗碰撞的。