Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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).
