After fixing the seed of a PRF, it computes a function from \(\{0,1\}^{\text {in }}\) to \(\{0,1\}^{\text {out }}\). Let’s consider the case where in \(=\) out. Some functions from \(\{0,1\}^{\text {in }}\) to \(\{0,1\}^{\text {out }}\) are invertible, which leads to the question of whether a PRF might realize such a function and be invertible (with knowledge of the seed). In other words, what if it were possible to determine \(x\) when given \(k\) and \(F(k, x)\) ? While this would be a convenient property, it is not guaranteed by the PRF security definition, even in the case of in \(=\) out. A function from \(\{0,1\}^{\text {in }}\) to \(\{0,1\}^{\text {out }}\) chosen at random is unlikely to have an inverse, therefore a PRF instantiated with a random key is unlikely to have an inverse.
A pseudorandom permutation (PRP) - also called a block cipher - is essentially a PRF that is guaranteed to be invertible for every choice of seed. We use both terms (PRP and block cipher) interchangeably. The term "permutation" refers to the fact that, for every \(k\), the function \(F(k, \cdot)\) should be a permutation of \(\{0,1\}^{i n}\). Instead of requiring a PRP to be indistinguishable from a randomly chosen function, we require it to be indistinguishable from a randomly chosen invertible function. \({ }^{2}\) This means we must modify one of the libraries from the PRF definition. Instead of populating the associative array \(T\) with uniformly random values, it chooses uniformly random but distinct values. As long as \(T\) gives distinct outputs on distinct inputs, it is consistent with some invertible function. The library guarantees distinctness by only sampling values that it has not previously assigned. Thinking of an associative array \(T\) as a key-value store, we use the notation \(T\).values to denote the set of values stored in \(T\).
Definition 6.6 (PRP syntax)
Let \(F:\{0,1\}^{\lambda} \times\{0,1\}^{\text {blen }} \rightarrow\{0,1\}^{\text {blen }}\) be a deterministic function. We refer to blen as the blocklength of \(F\) and any element of \(\{0,1\}^{\text {blen }}\) as a block.
We call \(F\) a secure pseudorandom permutation (PRP) (block cipher) if the following two conditions hold:
(Invertible given \(k\) ) There is a function \(F^{-1}:\{0,1\}^{\lambda} \times\{0,1\}^{\text {blen }} \rightarrow\{0,1\}^{\text {blen }}\) satisfying \[F^{-1}(k, F(k, x))=x,\] for all \(k \in\{0,1\}^{\lambda}\) and all \(x \in\{0,1\}^{\text {blen }}\)
(Security) \(\mathcal{L}_{\text {prp-real }}^{F} \approx \mathcal{L}_{\text {prp-rand }}^{F}\), where:
Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)
"\(T\). values" refers to the set \(\left \{ v\,\mid \,\exists x:T\left [ x \right ] =v \right \}\).
The changes from the PRF definition are highlighted in yellow. In particular, the \(\mathcal{L}_{\text {prp-real and }} \mathcal{L}_{\text {prf-real }}\) libraries are identical.
Discussion, Pitfalls
In the definition, both the functions \(F\) and \(F^{-1}\) take the seed \(k\) as input. Therefore, only someone with \(k\) can invert the block cipher. Think back to the definition of a PRF without the seed \(k\), it is hard to compute \(F(k, x)\). A block cipher has a forward and reverse direction, and computing either of them is hard without \(k\)!
\({ }^{2}\) As we will see later, the distinction between randomly chosen function and randomly chosen invertible function is not as significant as it might seem.
