Give a distinguisher to differentiate between PRP and RPO

Question

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:

1. 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$.
2. 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

1. PRP = pseudo random permutation
2. PRF = pseudo random function
3. RFO = random function oracle
4. 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.

Answer 1

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:

1. Let $q(n)$ be some polynomial.
2. Choose $q(n)$ many distinct elements from $\{0,1\}^n$. Call them $x_1,\dots,x_q$.
3. Query each $x_i$ to the oracle and record the result as $y_i$.
4. 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$.