PRF总是能抵抗碰撞吗？

Question

上下文:我们通常假设我们在实践中使用的哈希函数是两种:抗碰撞和伪随机。我想知道这些属性之间有什么关系。

问:伪随机函数是否总是具有抗碰撞能力？

Answer 1

首先，PRF是一个键控函数，而散列函数通常是无键的。因此，散列函数不能是PRF。

第二，安全的PRF可以在没有检测的情况下用一致随机函数交换，而寻找一致随机函数碰撞的最好方法是生日攻击。因此，如果PRF具有超多项式大的协域，那么它就具有抗碰撞能力，因为生日攻击需要超过多项式时间。

Answer 2

任何PRF都不一定是防撞的。如果PRF是PRP，而非块长度的输入，则PRP必然是冲突抵抗的，因为它的on-to函数，因此不可能将两个输入映射到相同的输出。当PRF不是PRP时，取决于它的输出长度，它可以是抗碰撞的。