PRF 是否總是抗碰撞的？

背景： 我們通常假設我們在實踐中使用的雜湊函式是：抗碰撞和偽隨機。我想知道這些屬性之間的關係是什麼。

問題： 偽隨機函式總是抗碰撞的嗎？

首先，PRF 是鍵控函式，而散列函式通常是無鍵的。因此，散列函式不能是 PRF。

其次，一個安全的 PRF 可以在不被檢測的情況下與一個統一的隨機函式交換，而找到一個統一的隨機函式的碰撞的最好方法是生日攻擊。因此，如果 PRF 具有超多項式大的共域，那麼它將是抗碰撞的，因為生日攻擊將花費更多的多項式時間。

確實避免了這個問題，但是抗碰撞性並不是偽隨機函式的真正考慮屬性。

查看 PRF 的定義：

F :: {0,1} k x {0,1} n –> {0,1} m

F ( 鍵, x ) = y

主要考慮因素是它模擬隨機函式的程度

$$ f(x) = y $$當給定一個隨機密鑰時。

引用自：https://crypto.stackexchange.com/questions/54134