# How is a PRP different from PRF? Both can be inverted to get the same input

PRP is said to be a bijective function which means that there is a one-to-one mapping with the output. And hence the output can be inverted using the decryption algorithm to get the same input.

Question is how's PRF different from that. If it is not bijective, how are we going to decrypt the message?

In counter mode it is said that we are using a PRF and not PRP (unlike CBC) i.e. we are not using the decryption capabilities of block cipher. What does this mean? We are anyway going to decrypt the message by XORing the IV counter and the key with the cipher text. Then why is it said that we are not using the decryption capabilities? and how is it different from PRP that has to have a decryption algorithm?

## 1 Answer

Indeed as you noted the primary difference between a PRP and a PRF is that a PRP must be bijective whereas a PRF doesn't have to. This also means that PRFs admit collisions, that is there may exist a key $$k$$ such that for two different inputs $$x,x'$$ $$F_k(x)=F_k(x')$$, whereas this is guaranteed to be impossible for PRPs.

In counter mode it is said that we are using a PRF and not PRP (unlike CBC) i.e. we are not using the decryption capabilities of block cipher.

A different way to think about counter-mode is to consider the keystream blinding the message. Then on the receiving end you reproduce the blinding and unblind the message.

Whereas with other modes like CBC you actually run your message through your function, which means you need to have a bijection in order to recover your original message unambigously.

• So, basically, if I understand correctly, in CBC, because of the chaining, the final cipher text has a one-to-one mapping with the original message text, whereas, in CTR, since each block is encrypted independently with the IV counter, key and the current block message text, there is no guarantee of uniqueness. A different message block and a different IV may produce the same cipher. Commented Oct 14, 2018 at 16:42
• @SaptarshiBasu No. The same message encrypted with different IVs under the same key will yield totally different ciphertexts in CBC. The intuition behind CBC is that you essentially blind the function input with the previous function output. Commented Oct 14, 2018 at 16:55