What is the difference between pseudorandom permutation/pseudorandom function/block cipher?

Question

What is the difference between;

• pseudorandom permutation
• pseudorandom function
• block cipher?

Very confused with the 3 terms and I am not good at advanced math. Can someone explain in plain word?

Answer 1

All three are families of functions. For example, $f_k(x) = k \oplus x$, where $\oplus$ is xor and $k$ and $x$ are 256-bit strings, is a family of functions; for any 256-bit string $k$, there is a function $f_k$ which given another 256-bit string $x$ returns the xor of $k$ and $x$. The input and output spaces need not be the same; we could imagine a family of functions $f_k$ from a 512-bit input $x$ to a 128-bit output $f_k(x)$, keyed by a 256-bit string $k$. Here is a small function family $g_k$ with a 1-bit key, a 2-bit input, and a 3-bit output:

\begin{equation*} \begin{array}{c|c} x & g_0(x) \\ \hline 00 & 111 \\ 01 & 000 \\ 10 & 100 \\ 11 & 110 \end{array} \qquad\qquad \begin{array}{c|c} x & g_1(x) \\ \hline 00 & 011 \\ 01 & 110 \\ 10 & 100 \\ 11 & 100 \end{array} \end{equation*}

A pseudorandom function family is a family of functions—say functions from 512-bit strings to 128-bit strings, indexed by a 256-bit key—which has the following property.

• Suppose I flip a coin 256 times to pick $k$—that is, I choose $k$ uniformly at random.

• Suppose I also pick a function $F$ from 512-bit strings to 128-bit strings uniformly at random from all $(2^{128})^{2^{512}}$ such functions, by flipping a lot of coins—enough to fill a book with $2^{512}$ pages so that each page has a 128-bit answer on it.

  ^{(Each table above has $4 = 2^2$ rows, because the input is 2-bits long, with a total of $3 \cdot 2^2 = 12$ bits of outputs written down, because there are three bits of output for each distinct input and $2^2$ distinct inputs. For a uniform random 512-bit-to-128-bit function, you need $2^{512}$ rows, and each row has $128$ bits of output, for a total of $128 \cdot 2^{512}$ bits just to write down one of the $(2^{128})^{2^{512}} = 2^{128 \cdot 2^{512}}$ different functions of that shape!)}

• I will pick one of these functions—$f_k$ or $F$, but you don't know which—and tell you what the value of the function is at any point you ask.

  • (Actually I don't need to fill the book up front; if I chose $F$, I can fill out the pages of the book lazily as I get queries from you.)

• You can't figure out whether I gave you a member of the function family, $f_k$, or a uniform random function, $F$.

In other words, the probability distribution on functions $f_k$, when the key $k$ is chosen uniformly at random, is very close—as far as computationally bounded decision algorithms can discern—to the probability distribution on functions $F$ chosen uniformly at random from all functions.

A pseudorandom permutation family is similar, except $f_k$ and $F$ are restricted to be permutations, i.e. their input and output spaces are the same, say the set of all 256-bit strings, and they map every input to a unique output so that there is also an inverse function. So there aren't quite as many possibilities for $F$—while there are $(2^{256})^{2^{256}}$ functions of 256-bit strings, there are only $2^{256}! \approx (2^{256}/e)^{2^{256}}$ permutations of 256-bit strings. A block cipher is just another term for pseudorandom permutation family, for the most part.*

Here's an example of a small permutation family $\pi_k$ for comparison—again the key is 1-bit, and the inputs and outputs are 2-bit strings:

\begin{equation*} \begin{array}{c|c} x & \pi_0(x) \\ \hline 00 & 00 \\ 01 & 11 \\ 10 & 10 \\ 11 & 01 \end{array} \qquad\qquad \begin{array}{c|c} x & \pi_1(x) \\ \hline 00 & 01 \\ 01 & 00 \\ 10 & 10 \\ 11 & 11 \end{array} \end{equation*}

Note that unlike the tables for $g_k$, each output appears exactly once in each table here, so we can flip each table around to get an inverse permutation.

We can interpret the bit strings as integers in (say) big-endian binary, and write this using the alternative notation $\pi_k = (\pi_k(0) \; \pi_k(1) \; \pi_k(2) \; \pi_k(3))$ for permutations, by saying that $\pi_0 = (0 \; 3 \; 2 \; 1)$ and $\pi_1 = (1 \; 0 \; 2 \; 3)$. Of course, for a pseudorandom permutation family like AES, the number of elements being permuted is not $2^2 = 4$ but $2^{128} = 340282366920938463463374607431768211456$, so we don't quite have enough space here to write AES down exhaustively in either notation even for a single key.

---

Actually it's not so much that a family of functions is or is not a pseudorandom function family, but rather we quantify your advantage as an adversary in playing that game. Specifically, we consider a decision algorithm $A(\mathcal O)$ which takes an oracle $\mathcal O$—which might be $f_k$ for uniform random $k$, or might be a uniform random $F$—and returns a decision in $\{0,1\}$, and we consider the distance between the probability that $A(\mathcal O)$ returns $1$ given $f_k$ for uniform random $k$ and the probability that it returns $1$ given uniform random $F$, called the advantage of $A$ as a PRF distinguisher:

\begin{equation*} \operatorname{Adv}^{\operatorname{PRF}}_f(A) := \lvert\Pr[A(f_k)] - \Pr[A(F)]\rvert. \end{equation*}

The PRP advantage is similar, but again $f_k$ and $F$ are restricted to be permutations. If it's very hard to tell whether the oracle is answering for $f_k$ or $F$, then this distance is nearly zero. Obviously, there is always a distinguisher with nonzero advantage: guess a key $\hat k$ at random and check whether $\mathcal O(x) = f_{\hat k}(x)$, but the advantage is very small, inversely proportional to the size of the key space. What's more interesting is distinguishers that have much higher advantage.

We conjecture for certain functions like HMAC-SHA256 or KMAC128—based on a long track record of failure by cryptanalysts to find good distinguishers—that this distance is small no matter what the adversary $A$ is, as long as $A$ makes an imaginable number of queries. (For example, we're not interested in an adversary that makes $2^{256}$ queries to the oracle, because nobody can do that.)

Then, when studying higher-level constructions like CBC-MAC, we set a bound on the forgery probability of the higher-level protocol in terms of a bound on the distinguishing advantage against the underlying PRF. That way, we can study whether something like CBC-MAC is a good way to build a MAC out of a PRF separately from whether AES is a good PRF.

‘Wait, AES is a good PRF?’, you say, ‘I thought AES was supposed to be a permutation!’ Well, any PRP makes a good PRF up to the birthday bound. Specifically, there's a theorem, sometimes called the PRF/PRP-switching lemma, that if $f_k$ is a $b$-bit permutation, then for any adversary $A$ making at most $q$ queries to the oracle, $$\operatorname{Adv}^{\operatorname{PRF}}_f(A) \leq \operatorname{Adv}^{\operatorname{PRP}}_f(A) + \binom{q}{2} 2^{-b}.$$ As long as $q \lll \sqrt{2^b} = 2^{b/2}$ so that $\binom{q}{2} = q(q - 1)/2 \lll 2^b$, the term $\binom{q}{2} 2^{-b}$ is very small. In other words, as long as our application keeps its data volume well below the birthday bound of $2^{b/2}$ blocks, a good pseudorandom permutation family like AES is nearly as good as a pseudorandom function family. This is, incidentally, the general reason why cryptosystems involving AES are not safe for more than a few petabytes of data under a single key—and for some of them the safe data volume limit is much lower.

---

* In some security analyses, it may be convenient to model a block cipher with a slightly stronger idealization than pseudorandomness: the ideal cipher model. Pseudorandomness is a kind of logic quantifier: for uniform random $k$, $f_k$ is hard to distinguish from a uniform random permutation, and it applies to specific function families like HMAC-SHA256. In the ideal cipher model, we study protocols where the function family itself is randomly chosen: for all distinct $k$, $f_k$ is an independent uniform random permutation. Like the random oracle model, it is a model for how adversaries are structured, rather than a ‘property’ that a specific computable thing like SHA-256 or HMAC-SHA256 can exhibit.

Answer 2

Pseudorandom permutation

Confusingly, nothing really gets permuted here in the classic definition of a permutation. It's more of a cryptographic twist on the common notion of permutation. The actual input/output behaviour is like:-

And each input is mapped to exactly one output value. The above diagram is simplistic in that the size of the inputs and outputs can be of the order of 128 bits or $0 \to (2^{128} -1)$. This is called a bijective or injective surjective function, and AES is an example.

Pseudorandom function

The idea here is that the output is random looking. Thus they behave as the following:-

Note the collision with 3, 4 & C. That occurs because random looking outputs collide randomly, similar to rolling pairs in dice. Output A cannot be attained due to the same collisions . But also note that these collisions are rare due to the size of the input/output domains (but not impossible depending on their actual sizes). This is called a non-injective non-surjective function. SHA-1 is an example.

Block cipher

This is simply a cipher function acting on multiple bytes at a time, rather than one. Like so, where each little square represents a byte:-

And it has to be à la pseudorandom permutation otherwise there would be collisions (as per above definition). That would mean that there would be multiple cipher texts matching up with a single plain text. And that's confusing. The above example might be DES, acting on 8 bytes at a time. AES is one too, but operates on 16 bytes at a time.

The opposite would be a function called "stream cipher" operating sequentially on one byte at a time, like RC4.

---

Certain minor simplifications have been made and some trivial liberties taken. This is to create a more strategic overview of the topic, and to offer a less 'mathy' answer.