Why do we use (pseudo) random permutations and not (pseudo) random functions for en- and decryption?

Why do we use pseudo random permutations and not pseudo random functions for encryption an decryption?

• Because we may not be able to uniquely decrypt with PRFs (because a function may map a larger set to a smaller one)? – SEJPM Apr 18 '18 at 15:18

We do use PRFs for encryption and decryption! We use them as stream ciphers to generate one-time pads.

For example, with the ChaCha20 stream cipher, the encryption of the $n^{\mathit{th}}$ message $m$ in a conversation is

\begin{equation*} \operatorname{ChaCha20-Encrypt}_{\;k}(n, m) = m \oplus p, \end{equation*} where $\oplus$ is xor, and the pad $p$ is generated by \begin{equation*} p = \operatorname{ChaCha20}_{\,k}(n \mathbin\Vert 0) \mathbin\Vert \operatorname{ChaCha20}_{\,k}(n \mathbin\Vert 1) \mathbin\Vert \dots. \end{equation*}

$\operatorname{ChaCha20}_{\,k}$ is the ChaCha20 core PRF under the key $k$.

Likewise for the AES-CTR stream cipher, but we use the PRP $\operatorname{AES256}_k$ approximating a PRF instead of the PRF $\operatorname{ChaCha20}_{\,k}$ to generate each block of the one-time pad. In all cases with this pattern, decryption conveniently turns out to be exactly the same procedure—which is a bonus for AES, because $\operatorname{AES256}_k$ is usually faster to compute than ${\operatorname{AES256}_k}^{-1}$, the latter of which is unnecessary to use in AES-CTR.

N.B.: If you're thinking about doing this in practice, please use it responsibly in an authenticated encryption scheme like crypto_secretbox_xsalsa20poly1305 or AES-GCM, not alone, unless you're very carefully designing an exotic protocol.

• The one-time pad model is to use ciphertext $c = m \oplus p$ for a message $m$, where $p$ is a uniform random pad the length of the message. Using a stream cipher to generate the pad $p$ is how we implement the model. Another model is the permutation model $c = \pi(m)$ where $\pi$ is a uniform random permutation of message-length bit strings. For short fixed-length messages we sometimes implement this model using block ciphers like AES, but, unlike pads, permutations are inconvenient to choose for arbitrary-length messages and must come with efficient forward and inverse algorithms. – Squeamish Ossifrage Apr 18 '18 at 21:30
• Pseudo random do dahs are not my forte, but is your one time pad different to the one in the 232 similarly tagged questions here? Your definition seems to be at odds with those. Might key stream be more accurate as suggested? – Paul Uszak Apr 19 '18 at 21:21
• Fetishization of the information-theoretic abstraction actively harms security by deluding people into the thinking they can do better than modern crypto engineering by avoiding it, when all they're doing is shooting themselves and their users in the foot with a confusion of ideas. – Squeamish Ossifrage Apr 21 '18 at 15:15
• Do you realise that your above comment doesn't actually say anything at all? – Paul Uszak Apr 21 '18 at 20:39