6.4: Relating PRFs and Block Ciphers
- Page ID
- 7351
In this section we discuss how to obtain PRFs from PRPs/block ciphers, and vice-versa.
Switching Lemma (PRPs are PRFs, Too!)
Imagine you can query a PRP on chosen inputs (as in the \(\mathcal{L}_{\text {prp-real }}\) library), and suppose the blocklength of the PRP is blen \(=\lambda\). You would only be able to query that PRP on a negligible fraction of its exponentially large input domain. It seems unlikely that you would even be able to tell that it was a PRP (i.e., an invertible function) rather than a PRF (an unrestricted function).
This idea can be formalized as follows.
Let \(\mathcal{L}_{\text {prf-rand }}\) and \(\mathcal{L}_{\text {prp-rand }}\) be defined as in Definitions \(6.1 \&\) 6.6, with parameters in \(=\) out \(=\) blen \(=\lambda\) (so that the interfaces match up). Then \(\mathcal{L}_{\text {prf-rand }} \approx \mathcal{L}_{\text {prp-rand }}\).
Proof
Recall the replacement-sampling lemma, Lemma 4.11, which showed that the following libraries are indistinguishable:
\(\mathcal{L}_{\text {samp-L}}\) samples values with replacement, and \(\mathcal{L}_{\text {samp-R}}\) samples values without replacement. Now consider the following library \(\mathcal{L}^{*}\) :
When we link \(\mathcal{L}^{*} \diamond \mathcal{L}_{\text {samp-L }}\) we obtain \(\mathcal{L}_{\text {prf-rand }}\) since the values in \(T[x]\) are sampled uniformly. When we link \(\mathcal{L}^{*} \diamond \mathcal{L}_{\text {samp-R }}\) we obtain \(\mathcal{L}_{\text {prp-rand }}\) since the values in \(T[x]\) are sampled uniformly subject to having no repeats (consider \(R\) playing the role of \(T\).values in \(\mathcal{L}_{\text {prp-rand }}\) ). Then from Lemma 4.11, we have: \[\mathcal{L}_{\text {prf-rand }} \equiv \mathcal{L}^{*} \diamond \mathcal{L}_{\text {samp-L }} \approx \mathcal{L}^{*} \diamond \mathcal{L}_{\text {samp-R }} \equiv \mathcal{L}_{\text {prp-rand }}\] which completes the proof.
Using the switching lemma, we can conclude that every PRP (with blen \(=\lambda\) ) is also a PRF:
Let \(F:\{0,1\}^{\lambda} \times\{0,1\}^{\lambda} \rightarrow\{0,1\}^{\lambda}\) be a secure PRP (with blen \(\left.=\lambda\right)\). Then \(F\) is also a secure \(PRF\)
Proof
As we have observed above, \(\mathcal{L}_{\text {prf-real }}^{F}\) and \(\mathcal{L}_{\text {prp-real }}^{F}\) are literally the same library. Since \(F\) is a secure PRP, \(\mathcal{L}_{\text {prp-real }}^{F} \approx \mathcal{L}_{\text {prp-rand }}^{F}\). Finally, by the switching lemma, \(\mathcal{L}_{\text {prp-rand }}^{F} \approx \mathcal{L}_{\mathrm{prf}-\mathrm{rand}}^{F}\). Putting everything together:
\[\mathcal{L}_{\text {prf-real }}^{F} \equiv \mathcal{L}_{\text {prp-real }}^{F} \approx \mathcal{L}_{\text {prp-rand }}^{F} \approx \mathcal{L}_{\text {prf-rand }}^{F}\]
hence \(F\) is a secure PRF.
Keep in mind that the switching lemma applies only when the blocklength is sufficiently large (at least \(\lambda\) bits long). This comes from the fact that \(\mathcal{L}_{\text {samp-L }}\) and \(\mathcal{L}_{\text {samp-R }}\) in the proof are indistinguishable only when sampling with long (length- \(\lambda\) ) strings (look at the proof of Lemma \(4.11\) to recall why). Exercise \(6.14\) asks you to show that a random permutation over a small domain can be distinguished from a random (unconstrained) function; so, a PRP with a small blocklength is not a PRF.
Constructing a PRP from a PRF: The Feistel Construction
How can you build an invertible block cipher out of a PRF that is not necessarily invertible? In this section, we show a simple technique called the Feistel construction (named after IBM cryptographer Horst Feistel).
The main idea in the Feistel construction is to convert a not-necessarily-invertible function \(F:\{0,1\}^{n} \rightarrow\{0,1\}^{n}\) into an invertible function \(F^{*}:\{0,1\}^{2 n} \rightarrow\{0,1\}^{2 n}\). The function \(F^{*}\) is called the Feistel round with round function \(F\) and is defined as follows:
No matter what \(F\) is, its Feistel round \(F^{*}\) is invertible. Not only that, but its inverse is a kind of "mirror image" of \(F^{*}\) :
Note how both the forward and inverse Feistel rounds use \(F\) in the forward direction!
Let’s see what happens in the Feistel construction with a trivial round function. Consider the constant function \(F(y)=0^{n}\), which is the "least invertible" function imaginable. The Feistel construction gives:
\[\begin{aligned} F^{*}(x \| y) &=y \|(F(y) \oplus x) \\ &=y \|\left(0^{n} \oplus x\right) \\ &=y \| x \end{aligned}\]
The result is a function that simply switches the order of its halves - clearly invertible.
Let’s try another simple round function, this time the identity function \(F(y)=y\). The Feistel construction gives:
\[\begin{aligned} F^{*}(x \| y) &=y \|(F(y) \oplus x) \\ &=y \|(y \oplus x) \end{aligned}\]
This function is invertible because given \(y\) and \(y \oplus x\) we can solve for \(x\) as \(y \oplus(y \oplus x)\). You can verify that this is what happens when you plug \(F\) into the inverse Feistel construction.
We can also consider using a round function \(F\) that has a key/seed. The result will be an \(F^{*}\) that also takes a seed. For every seed \(k, F^{*}(k, \cdot)\) will have an inverse (which looks like its mirror image).
Now suppose \(F\) is a secure PRF and we use it as a Feistel round function, to obtain a keyed function \(F^{*}\). Since \(F^{*}(k, \cdot)\) is invertible for every \(k\), and since \(F^{*}\) uses a secure PRF in some way, you might be tempted to claim that \(F^{*}\) is a secure PRP. Unfortunately, it is not! The output of \(F^{*}\) contains half of its input, making it quite trivial to break the PRP-security of \(F^{*}\)
We can avoid this trivial attack by performing several Feistel rounds in succession, resulting in a construction called a Feistel cipher. At each round, we can even use a different key to the round function. If we use \(k_{1}\) in the first round, \(k_{2}\) in the second round, and so on, then \(k_{1}, k_{2}, \ldots\) is called the key schedule of the Feistel cipher. The formal definition of an \(r\)-round Feistel cipher is given below:
Because each round is invertible (given the appropriate round key), the overall Feistel cipher is also invertible. Note that the inverse of the Feistel cipher uses inverse Feistel rounds and reverses the order of the key schedule.
Surprisingly, a 3-round Feistel cipher can actually be secure, although a 2-round Feistel cipher is never secure (see the exercises). More precisely: when \(F\) is a secure PRF with in \(=\) out \(=\lambda\), then using \(F\) as the round function of a 3-round Feistel cipher results in a secure PRP. The Feistel cipher has blocklength \(2 \lambda\), and it has a key of length \(3 \lambda(3\) times longer than the key for \(F)\). Implicitly, this means that the three round keys are chosen independently.
If \(F:\{0,1\}^{\lambda} \times\{0,1\}^{\lambda} \rightarrow\{0,1\}^{\lambda}\) is a secure \(P R F\), then the 3-round Feistel cipher \(\mathbb{F}_{3}\) (Construction 6.11) is a secure PRP.
Unfortunately, the proof of this theorem is beyond the scope of this book.