6.6☆: Strong Pseudorandom Permutations

Last updated
Save as PDF

Page ID: 86460

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Since a block cipher \(F\) has a corresponding inverse \(F^{-1}\), it is natural to think of \(F\) and \(F^{-1}\) as interchangeable in some sense. However, the PRP security definition only guarantees a security property for \(F\) and not its inverse. In the exercises, you will see that it is possible to construct \(F\) which is a secure PRP, whose inverse \(F^{-1}\) is not a secure PRP!

It would be very natural to ask for a PRP whose \(F\) and \(F^{-1}\) are both secure. We will later see applications where this property would be convenient. An even stronger requirement would allow the distinguisher to query both \(F\) and \(F^{-1}\) in a single interaction (rather than one security definition where the distinguisher queries only \(F\), and another definition where the distinguisher queries only \(F^{-1}\) ). If a PRP is indistinguishable from a random permutation under that setting, then we say it is a strong PRP (SPRP).

In the formal security definition, we provide the calling program \(t\) wo subroutines: one for forward queries and one for reverse queries. In \(\mathcal{L}_{\text {sprp-real }}\), these subroutines are implemented by calling the PRP or its inverse accordingly. In \(\mathcal{L}_{\text {sprp-rand, we emulate the }}\) behavior of a randomly chosen permutation that can be queried in both directions. We maintain two associative arrays \(T\) and \(T_{i n v}\) to hold the truth tables of these permutations, and sample their values on-demand. The only restriction is that \(T\) and \(T_{i n v}\) maintain consistency \(\left(T[x]=y\right.\) if and only if \(\left.T_{i n v}[y]=x\right)\). This also ensures that they always represent an invertible function. We use the same technique as before to ensure invertibility.

Definition 6.13 (SPRP security)

Let \(F:\{0,1\}^{\lambda} \times\{0,1\}^{\text {blen }} \rightarrow\{0,1\}^{\text {blen }}\) be a deterministic function. We say that \(F\) is a secure strong pseudorandom permutation \((\boldsymbol{S P R P})\) if \(\mathcal{L}_{\mathrm{sprp}-\mathrm{real}}^{F} \approx \mathcal{L}_{\mathrm{sprp}-\mathrm{rand}}^{F}\), where:

Earlier we showed that using a PRF as the round function in a 3-round Feistel cipher results in a secure PRP. However, that PRP is not a strong PRP. Even more surprisingly, adding an extra round to the Feistel cipher does make it a strong PRP! We present the following theorem without proof:

Theorem 6.14 (Luby-Rackoff)

If \(F:\{0,1\}^{\lambda} \times\{0,1\}^{\lambda} \rightarrow\{0,1\}^{\lambda}\) is a secure PRF, then the 4-round Feistel cipher \(\mathbb{F}_{4}\) (Construction 6.11) is a secure SPRP.