Leaving aside the problem of how to compute the inverse of a PRF F, may we use it also as a PRP?

The reciprocal of this statement is true, see for instance Katz and Lindell, Proposition 3.27, when the input length of F is sufficiently large. However, in practice to build a PRP from a PRF people use a Feistel network. This would address the problem of making the PRF invertible.

Leaving aside the invertibility I guess the same proof for PRP $\implies$ PRF is useful here. Am I right?

  • $\begingroup$ See this What is difference between PRG, PRF, and PRP $\endgroup$
    – kelalaka
    Nov 28, 2018 at 10:41
  • $\begingroup$ @kelalaka I already read it. My quesion is not really adressed there $\endgroup$ Nov 28, 2018 at 10:50
  • $\begingroup$ Didn't you answer your own question by mentioning Feistel networks? $\endgroup$
    – forest
    Nov 28, 2018 at 11:00
  • $\begingroup$ @forest no, because they solve the problem of invertibility, but I say: "leaaving aside the problem of how to compute the inverse of a PRF"... $\endgroup$ Nov 28, 2018 at 11:09
  • $\begingroup$ @Javier They don't solve the problem of invertibility, they just use a non-invertible PRF to construct an invertible PRP. From Wikipedia, "One advantage of the Feistel model compared to a substitution–permutation network is that the round function $\operatorname{F}$ does not have to be invertible." $\endgroup$
    – forest
    Nov 28, 2018 at 11:11

1 Answer 1


If the output domain is large enough so that the probability of getting a collision in the PRF is negligible, then the output of a PRP and PRF are indistinguishable. Thus, in principle, the answer is yes - you can interchange these freely (under the above condition).

Having said that, it's unclear to me why you would want a non-invertible PRP rather than a PRF. Typically, a PRF is better for cryptographic constructions, being easier to analyze and giving better bounds, and the only time we use a PRP is when we want to invert. Maybe there is an example of a use of a PRP specifically when inversion is not needed, but I don't think I've ever seen one (and can't really think of where it would be helpful).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.