Pseudorandom Permutation equals to PRF?

Question

I stuck on the same problem in a cryptography, as stated in this question

I found following statement in famous textbook by J. Katz (main wiki PRP article refers to this textbook)

PROPOSITION 3.27 If F is a pseudorandom permutation and additionally L-input(n) >= n, then F is also a pseudorandom function.

So the question is extremely simple, but I spent hours trying to find an answer. If Fk(x) - is a PRP which takes n-length input, uniform n-length key k, and x - as an input n-bit string. How it can be a pseudorandom function?!

Permutation means F(00000) = 00000 ? So the function just reorder given input bits in pseudorandom manner determined by key K? If not, can someone explain what actually does a PRP? And what is the difference with PRF? Except invertibility.

Answer 1

A psuedorandom permutation is a permutation in the "arrangements" sense if you examine all possible n-length blocks. It is not a shuffling of the block that you input to the function. The function takes the whole block and replaces it with another, completely different block.

To see this, picture encrypting a counter using a blockcipher with a given key. It would spit out one random block after another. Encrypt the same counter sequence using a different key, and it will spit out different random blocks. If you were to encrypt all possible values of the counter under the two different keys and examine the two resulting sets of ciphertexts, you would see two different arrangements of all n-length blocks. This is the "permutation" part of psuedorandom permutation.

The prototypical permutation producing algorithm is the Fisher-Yates shuffle. You could view a psuedorandom permutation like applying a Fisher-Yates shuffle to the sequence of counter blocks, where each entry is one possible n-length block.

As for the difference between a prp and a prf, I'm pretty sure we have an answer to that on the site already.

Answer 2

It can be a pseudorandom function by usually not preserving number-of-ones.
flip-the-middle-bit gives a permutation on {0,1}⁵ which does not send 00000 to 00000.
No. ​ Instead, the function just reorders its domain
"in pseudorandom manner determined by key K".

A PRP computes a pseudorandom permutation on its domain, whatever that domain may be:
In particular, even if the domain happens to be a function-space $\big(\hspace{-0.04 in}$like {0,1}^{0,1,2,3,4}$\hspace{-0.03 in}\big)$,
that does not mean it instead computes the action of a
pseudorandom permutation on the function-space's domain.


In addition to being invertible, it must come with an efficient(-given-the-key) inversion algorithm and indistinguishability must hold even when the adversary has an inversion oracle.