# 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:

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.

• "a PRF can be considered as a PRP" Not at all. A PRF is not guaranteed to be a permutation and thus is most certainly not a PRP. – Maeher Feb 15 '19 at 13:00
• Could you clarify what you mean by RPO and RFO? – Maeher Feb 15 '19 at 13:02
• That statement is still incorrect. A PRF is not a PRP, even if you drop the requirement of being invertible. It is not a permutation. What you mean is maybe that it is indistinguishable from a PRP? – Maeher Feb 15 '19 at 13:04
• @Maeher yes that's what i mean – Rodrigo Feb 15 '19 at 13:06
• cseweb.ucsd.edu/~mihir/cse207/w-se.pdf – Rodrigo Feb 15 '19 at 13:22

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

• May be not meaningful; if there is an oracle that given y returns x, inverse Oracle, does this give more info to distinguish? – kelalaka Feb 15 '19 at 14:30
• @kelalaka A random function does not have an inverse with overwhelming probability. So it's not possible to provide such an oracle. Unless I misunderstand your comment. – Maeher Feb 15 '19 at 14:49
• maybe kelalaka was referring to an Oracle that, on input y, samples from the set of pre preimages – Geoffroy Couteau Feb 15 '19 at 17:27
• great answer! I suggest using $\{0,1\}^{l(n)}$ with $l(n) \ge n$ for the output space to make it more general. The collision probability can be also estimated for $q(n) \le \sqrt(2 \cdot 2^{l(n)})$ as greater than $\frac{q(n)(q(n)-1)}{4 \cdot 2^{l(n)}}$. Thanks for your help – Rodrigo Feb 24 '19 at 0:34