The Elegance of the Feistel Cipher

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:

1. (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 }}$

2. (Security) $\mathcal{L}_{\text {prp-real }}^{F} \approx \mathcal{L}_{\text {prp-rand }}^{F}$, where:

"$T$. values" refers to the set $\left \{ v\,\mid \,\exists x:T\left [ x \right ] =v \right \}$.

Discussion, Pitfalls