My question is related to this:

Collision-resistant Pseudorandom function

Assume we have a pseudorandom function as follows: $PRF: \{0,1\}^{l}\times\{0,1\}^{t}\rightarrow\{0,1\}^{m}$, where $l$ is the security parameter. Also, assume $k,k'\leftarrow \{0,1\}^{l}$ are two independent random keys and $r_1,r_2 \leftarrow \{0,1\}^{t}$ are two independent random values.

Question 1: What is the probability that $PRF(k,r_1)=PRF(k',r_2)$

Question 2: Would the probability in the question 1 be different if we replace $r_1, r_2$ with a fixed value $i$, probability that $PRF(k,i)=PRF(k',i)$?

  • $\begingroup$ The probability obviously depends on what the PRF is, but of course it can't differ too much from what you'd get with a random function... $\endgroup$
    – fkraiem
    Jan 31 '17 at 12:33
  • $\begingroup$ Wouldn't it simply be the probability of a collision in $(k,r_{1}),(k',r_{2})$ or a collision in the output due to pigeonhole principle? $\frac{1}{2^{l+t}} + \frac{1}{2^{m}}$ $\endgroup$
    – user13741
    Jan 31 '17 at 15:34
  • $\begingroup$ @fkraiem "The probability obviously depends on what the PRF is". Yes, the problem was that I though the output domain of PRF must be large enough. But its definition does not imply that. So we need a collision-resistant PRF, in this case probability that $PRF(k,i)=PRF(k',i)$ is $1/t$ where $t$ is output size. $\endgroup$
    – user153465
    Jan 31 '17 at 15:39
  • $\begingroup$ @fkraiem The paper in : dl.acm.org/citation.cfm?id=1102146 shows how to construct a collision-resistant PRF. But it's not clear to me why any PRF with a large enough output domain would not work. $\endgroup$
    – user153465
    Jan 31 '17 at 15:42

You claim that $k$, $k'$ are chosen independently and uniformly. Assuming these keys are used nowhere else except as PRF keys in this way, and that the length of the PRF keys are at least the security parameter, then you can apply the security of the PRF. Collision resistance doesn't seem relevant to me if the key portion of the PRF input is guaranteed to be chosen randomly. The answer to your question is negligibly close to the answer to:

  • what is the probability $R(r_1) = R'(r_2)$ where $R$ and $R'$ are independent random functions?

Here it is clear that the distribution over $r_1$ and $r_2$ is irrelevant. The outputs $R(r_1)$ and $R'(r_2)$ are distributed uniformly/independently. So they are equal with probability $1/2^m$.

So the answer to your question seems to be ``negligibly close to $1/2^m$'' where the negligible amount is the security loss of your PRF. If $m$ is large then it is possible the PRF security loss may overwhelm the $1/2^m$ term. If $m$ is small (e.g., constant), then the security loss probably dwarfs the $1/2^m$ term.


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.