Give a distinguisher to differentiate between PRP and RPO I have understood the proof that shows that a PRP is a PRF except for negligible probability $\frac{q(n)^2}{2^{-l(n)}}$. My computations suggest me that the same argument, perhaps with minor mathematical details, can show that a PRF can be treated as a PRP (if we forget about the fact that a PRP needs to be a DPT computable permutation while a PRF needs not).

Now I stumble upon this question:


  Show that there is a PPT-adversary which distinguished a PRP F from  RFO with a negligible, but non-zero advantage.


My problem is to give the code in the distinguisher side. Let me phrase it:


Alice picks $b \stackrel{u}{\in} \{0,1\}$. If $b = 0$ sends to Eve the RFO and if $b = 1$ sends to Eve the PRP $F$.
Here I need to describe what the distinguisher $D$ does.


I guess that I should make $D$ query the oracle he receives a polynomial number of time $q(n)$ defined by its efficiency bound. But what can be the details of the construction?

Glossary


PRP = pseudo random permutation
PRF = pseudo random function
RFO = random function oracle
RPO = random permutation oracle


A RFO is essentially supposed to generate a random function in the sense that when a new input (it has not been seen before) it will assign to this input a random output. The RPO is similar to this construction but ensures that the output have not been used before for other inputs, so that the generated function is injective.
As you do not specify what the domain of the function is, I'm going to assume that we're talking about functions of the form $f:\{0,1\}^n \to \{0,1\}^n$.

The distinguisher works as follows:


Let $q(n)$ be some polynomial.
Choose $q(n)$ many distinct elements from $\{0,1\}^n$. Call them $x_1,\dots,x_q$.
Query each $x_i$ to the oracle and record the result as $y_i$.
If there exists any $y_i=y_j$ with $i\neq j$, output $0$, otherwise output $1$.


If the oracle is a PRP, then it is by definition a permutation (i.e. has no collisions) and since $x_i\neq x_j$ for all $i\neq j$ the distinguisher outputs $1$ with probability $1$.

If the oracle is a truly random function, then each $y_i$ is uniformly and independently distributed. The probability that there is at least one collision among $q(n)$ randomly sampled elements of $\{0,1\}^n$ is $$1-\prod_{i=1}^{q(n)}\frac{2^n-i}{2^n} \geq 1$$ and therefore the distinguisher will output $1$ with probability $1-\varepsilon(n)$ for some $\varepsilon(n)\geq0$.