1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "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. $\endgroup$ – Maeher Feb 15 at 13:00
  • $\begingroup$ Could you clarify what you mean by RPO and RFO? $\endgroup$ – Maeher Feb 15 at 13:02
  • $\begingroup$ 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? $\endgroup$ – Maeher Feb 15 at 13:04
  • $\begingroup$ @Maeher yes that's what i mean $\endgroup$ – Javier Feb 15 at 13:06
  • $\begingroup$ cseweb.ucsd.edu/~mihir/cse207/w-se.pdf $\endgroup$ – Javier Feb 15 at 13:22
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ May be not meaningful; if there is an oracle that given y returns x, inverse Oracle, does this give more info to distinguish? $\endgroup$ – kelalaka Feb 15 at 14:30
  • $\begingroup$ @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. $\endgroup$ – Maeher Feb 15 at 14:49
  • $\begingroup$ maybe kelalaka was referring to an Oracle that, on input y, samples from the set of pre preimages $\endgroup$ – Geoffroy Couteau Feb 15 at 17:27
  • $\begingroup$ 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 $\endgroup$ – Javier Feb 24 at 0:34

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.