Assume we have two pseudorandom functions $PRF$ and $PRF'$ defined as follows:

$PRF: \{0,1\}^{n}\times \{0,1\}^{m}\rightarrow \{0,1\}^{n}$

$PRF': \{0,1\}^{n}\times \{0,1\}^{m}\rightarrow \mathtt{F}_p$

where $p$ is a large prime number, $|p|=l$, and $l$, $n$ are security parameters.

Question 1: Is $PRF'$ secure and does it meet the standard definition of pseudorandom function?

if yes, then

Question 2: Are these two pseudorandom functions are different in terms of the level of security and the probability that collision occurs?

  • 1
    $\begingroup$ I'm semi-sure the definition of a PRF is independent of the actual sets. As such the answer to Q1 would be "yes" and the answer to Q2 would be "$\sqrt{p}$ vs n/2" $\endgroup$
    – SEJPM
    Feb 5 '17 at 15:53
  • $\begingroup$ What's the standard definition? $\endgroup$
    – fkraiem
    Feb 5 '17 at 17:36
  • $\begingroup$ @fkraiem I meant the definition provided in the crypto. textbooks, e.g. introduction to modern cryptography or foundation of cryptography. $\endgroup$
    – user153465
    Feb 5 '17 at 20:10
  • $\begingroup$ Well then, what is this definition? $\endgroup$
    – fkraiem
    Feb 5 '17 at 20:16

$F_p$ has a one to one mapping with the set of integers $[0, p)$. $\{0, 1\}^n$ has a one to one mapping with the set of integers $[0, 2^n)$. Their sizes are respectively $p$ and $2^n$.

Both $F_p$ and $\{0, 1\}^n$ are common (co)domains chosen due to nice properties in either efficiency, easy analysis or ease of use in the greater scheme of things. But to analyse a PRF these are fundamentally the same.

You are mapping one set to another. This mapping must be indistinguishable from a random oracle, within security bounds. For the analysis the only fundamental property are the sizes and distributions of the sets you're mapping, not what those sets actually contain.

The birthday attack on secure PRFs roughly dictates that you'll find a collision after $\sqrt{s}$ random outputs, where $s$ is the size of the codomain. So for your question respectively $\sqrt{p}$ and $2^{n/2}$.


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.