Can an encryption scheme (deterministic or not) be viewed as a pseudorandom permutation taking as input a message and returning a value of the same bit-encoding length?

  • $\begingroup$ Did you mean a pseudorandom permutation? A pseudorandom function isn't very useful for encryption since it isn't invertible (so it's not possible to decrypt). Also, consider that an encryption scheme returning an output exactly as long as its input must necessarily be deterministic.. what does that imply about some of its security properties? $\endgroup$ – Thomas Jul 4 '13 at 17:08
  • $\begingroup$ There is probabilistic encryptions schemes kaking as input a randomized Iv for each message to encrypt. My question is relative to pseudorandom function, by considering only the behaviour of the encryption, not the decryption. If you take the example of a block-cipher, it is computationally indistinguishable from a random function, so we can consider it as a pseudorandom function. However a block-cipher has the behaviour of a permutation... $\endgroup$ – Dingo13 Jul 4 '13 at 17:13
  • $\begingroup$ The IV is conventionally part of the output but not of the input (which is why it's called a randomized encryption scheme - randomization is a property of the primitive, else it would still be deterministic). Anyway, I think I understand better, you want to ask to what extent a PRP can be modelled as PRF, since their security properties overlap, right?. One will necessarily need to instantiate those with at least some concrete security parameters such as input/output length. For instance, you are correct that a 128-bit PRP cannot be distinguished from a PRF, but a 64-bit PRP certainly can. $\endgroup$ – Thomas Jul 4 '13 at 17:22
  • $\begingroup$ "you want to ask to what extent a PRP can be modelled as PRF, since their security properties overlap, right?" Not. Thank you and sorry for my mistakes. My question can be referred to a pseudorandom permutation, you are right. I edit the question. $\endgroup$ – Dingo13 Jul 4 '13 at 17:25
  • $\begingroup$ @Thomas: PRFs are quite useful for encryption, actually... if you use a PRF in a 4-round Feistel network, you've just built a strong PRP. $\endgroup$ – Reid Sep 4 '13 at 13:36

The term "pseudorandom permutation" is normally used for a family of (computable) bijections $f_k : M \to M$, where $M$ is some finite set, and usually $M = \{0,1\}^n$. (Usually we also have a computable inverse for each $f_k$, and some security properties.)

If we stretch the meaning a bit, we can expand this to any finite set $M$, like "the set of all byte strings shorter than $2^{100}$ bytes" (i.e. more than anything you would ever want to encrypt. But when using this set, all common encryption schemes are, while permutations, not pseudorandom, because we can guess from the length of the output to the length of the input.

If we instead use as $M$ a set like "the set of all byte strings of length 1 KB", any good deterministic encryption scheme restricted to $M$ indeed should fulfill the properties of a random permutation on $M$.

A non-deterministic encryption scheme first will have to expand the ciphertext (e.g. by writing the IV into it), and secondly is not a permutation (a permutation is deterministic).

If we can extract the randomness part and use it as a separate input to a deterministic function (or, as a chooser for a family member), we can treat the encryption itself just like before.

But normally the term "random permutation" is used only for the actual building blocks of such encryption schemes, also named "block cipher".

| improve this answer | |

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.