怎麼證明second preimage resistant不代表collision resistant？

01-25

有道題讓我證明或反證這句話……If H is 2nd preimage resistant, then H is also collision resistant
我知道反過來是正確的，那麼如果這個也正確那麼兩者就相等了，沒必要分別定義，那麼應該是不正確，但是不知道怎麼證明……求反例……

idea: 考慮定義，找一個不滿足collision resistant但是滿足second pre-image resistant的Hash函數

下面證明用的英文，應該不難懂……

Claim: There exists a Hash function h" which is second pre-image resistant but not collision resistant.

Proof:

Let $h(x)$ be a collision resistant hash function. Define another hash function $h$ as

$h$

h"(x) is NOT collision resistant. (trivial from the definition above)

However, in the security experiment for second pre-image resistance, the challenge text ( x*, h"(x*) ) is chosen uniformly at random. Thus $Pr[x^*= 0^l lor x^*= 1^l] le negl(n)$

If x* does NOT fall on either of the special values, because of the collsion resistance of h(x), it is hard for any ppt adversary A to find a second pre-image x" such that h"(x*) = h"(x"), namely,

$Pr[x$ ,

where B is a ppt second preimage adversary against h.

Thus we finally have $Pr[x$

So there exists a hash function h" as defined which is second pre-image resistant but not collision resistant.

對於玄星給出的例子有一點存疑。其中說h"(x)是抗碰撞的，僅僅從h"(x)的定義一筆帶過。但是實際上根據CRHF定義，如果一個函數是抗碰撞的，指的是任何多項式時間敵手，不能在多項式時間內，以不可忽略概率找到x1≠x2，且h(x1)=h(x2)，這樣即為collision resistant。這代表可能存在不同輸入但是對應相同輸出，只要無法在多項式時間內以不可忽略概率找到即可滿足條件。對於h"(x)，如果僅僅存在一組碰撞值，對於一個敵手找到這組碰撞的概率依然是1/2^l 是一個可忽略概率，依然滿足collision resistant的條件。所以對於這個函數的構造方式，不足以證明不滿足是Collision Resistant 卻滿足 2nd Pre-image Resistant.