5
$\begingroup$

Context: We usually assume that the hash functions we use in practice are both: collision resistant and pseudorandom. I wonder what's the relation between those properties.

Question: Is a pseudo random function always collision resistant?

$\endgroup$
1
  • $\begingroup$ Possible counterexample: the MD5 compression function, which is conjectured to be a PRF but which probably isn't collision-resistant. However, I'm not sure it fails the technical property of keyed collision-resistant hash family, and the way its PRFness is used to justify NMAC security is a little wacky, so… I don't know! $\endgroup$ – Squeamish Ossifrage Dec 21 '17 at 18:32
2
$\begingroup$

First, a PRF is a keyed function, meanwhile a hash function is usually keyless. So, a hash function cannot be a PRF.

Second, a secure PRF can be swapped with a uniform random function without detection, and the best way to find a collision of a uniform random function is the birthday attack. So, if the PRF has superpolynomially large codomain, then it would be collision-resistant, since the birthday attack would take more than polynomial-time.

$\endgroup$
7
  • 1
    $\begingroup$ I am considering the keyed setting here. Could you support your second statement by providing an algorithm that given access to a collision finding oracle distinguishes the PRF from a random function? $\endgroup$ – mti Dec 21 '17 at 16:43
  • $\begingroup$ @mti: I believe the reasoning is "truly random functions with large outputs don't have efficient oracles that find collisions, hence if you have one, you don't have a truly random function" $\endgroup$ – poncho Dec 21 '17 at 16:47
  • 1
    $\begingroup$ @poncho: What do you mean by "efficient oracle"? Do you mean "efficient algorithm"? Then you are saying that there is no efficient algorithm for finding collisions in a PRF, right? I would like to understand why! Again, I think what one has to show here is that given an algorithm for computing collisions, we can construct an algorithm for distinguishing the PRF from a randomly chosen function. $\endgroup$ – mti Dec 21 '17 at 17:23
  • 1
    $\begingroup$ In more technical terms: Suppose you had a collision-finder $A(k)$ with cost $C$ for which $\operatorname{Adv}^{\operatorname{Coll}}_H(A) = \Pr[x_0 \ne x_1, H_k(x_0) = H_k(x_1)]$ is significantly better than the birthday probability for $q$, where $k$ is uniform random and $(x_0, x_1) = A(k)$. How does that let us make a PRF-distinguisher $B(f)$ making some $q$ calls to $f$ for which $\operatorname{Adv}^{\operatorname{PRF}}_H(B) = \Pr[B(H_k) = 1] - \Pr[B(F) = 1]$ is nontrivial, where $F$ is a uniform random function? Our desired $B$ can't just pass the unknown key $k$ to $A$. $\endgroup$ – Squeamish Ossifrage Dec 21 '17 at 18:12
  • $\begingroup$ @SqueamishOssifrage: good question; by "collision-resistant", do you mean against adversaries that don't know the key, or ones that do? My comment assumed that the oracle didn't need to know the key; I would agree that the lack of resistance against adversaries that do know the key isn't a necessary property. $\endgroup$ – poncho Dec 21 '17 at 18:48
0
$\begingroup$

Avoiding the question really, but collision resistance isn't really a considered property of Pseudo-random functions.

Looking at the definition of a PRF:

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

F ( key, x ) = y

the main consideration is how well it emulates the random function [f(x) = y] when given a random key.

$\endgroup$
1
0
$\begingroup$

Not any PRF is necessarily collision resist. If the PRF is a PRP, than for inputs of length of block-length, the PRP is necessarily collision resist because its on-to function, so it is impossible that two inputs are mapped to the same output. When the PRF is not PRP, depends on its output length, it can be collision resist.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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