1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ AES is a 128-bit PRP, can you find a key where an all 0 input results in an all 0 output? or even where any input and output are the same? $\endgroup$ – Richie Frame Feb 17 '17 at 9:20
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

It can be a pseudorandom function by usually not preserving number-of-ones.
flip-the-middle-bit gives a permutation on {0,1}5 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.

$\endgroup$

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.