- Let $A$ be any distinguisher running in time $t$, and making $q$ oracle
- queries. Then:
- \begin{eqnarray*}[rl]
- \Adv{prf}{F}(A)
- & = \Pr[A^{F_K(\cdot)} = 1] - \Pr[A^{R(\cdot)} = 1] \\
- & = \Pr[A^{F_K(\cdot)} = 1] - \Pr[A^{P(\cdot)} = 1] +
- \Pr[A^{P(\cdot)} = 1] - \Pr[A^{R(\cdot)} = 1] \\
- & = \Adv{prp}{F}(A) + \Pr[A^{P(\cdot)} = 1] - \Pr[A^{R(\cdot)} = 1] \\
- & = \Adv{prp}{F}(A) + \Pr[A^{R(\cdot)} = 0] - \Pr[A^{P(\cdot)} = 0].
- \end{eqnarray*}
- Now we need to bound the quantity $\Pr[A^{R(\cdot)} = 0] - \Pr[A^{P(\cdot)}
- = 0]$. Let $D$ be the event that all of the \emph{distinct} oracle queries
- to $R$ yield distinct results. Then
+ Let $A$ be an adversary which distinguishes~$F$ from a pseudorandom
+ function in time~$t$, after making $q$ oracle queries. We consider a
+ sequence of games $\G{i}$ played with the adversary. In each game $\G{i}$,
+ let $S_i$ be the event that the adversary returns~$1$ at the end of the
+ game.
+
+ Game~$\G0$ is the `random function' game. We given $A$ an oracle
+ containing a random function $R \inr \Func{L}{L}$.
+
+ Game~$\G1$ is the `PRF' game. We give $A$ an oracle which computes
+ $F_K(\cdot)$ for some randomly chosen $K \inr \{0, 1\}^k$.
+
+ By definition, then,
+ \[ \Adv{prf}{F}(A) = \Pr[S_1] - \Pr[S_0]. \]
+\end{slide}
+
+\begin{slide}
+ \head{PRPs are PRFs, \seq: proof (cont.)}
+
+ Let $x_0, x_1, \ldots, x_{q-1}$ be the oracle queries made by $A$, and let
+ $y_0, y_1, \ldots, y_{q-1}$ be the corresponding responses.
+
+ Game~$\G2$ works in the same way as $\G0$, except that if there is a
+ \emph{collision} in the query replies (i.e., $y_i = y_j$ but $x_i \ne x_j$
+ for any $0 \le i, j < q$) then we stop the game immediately. Let $F_2$ be
+ the event that this occurs.
+
+ Because $\G2$ behaves exactly the same as $\G0$ unless $F_2$ occurs, we
+ must have
+ \[ \Pr[S_2 \land \lnot F_2] = \Pr[S_0 \land \lnot F_2] \]
+ so we invoke Lemma~\ref{lem:shoup} and discover that
+ \[ |{\Pr[S_2]} - \Pr[S_0]| \le \Pr[F_2]. \]
+ Using the earlier result on collisions, it's easy to see that
+ \[ \Pr[F_2] \le \frac{q(q - 1)}{2^{L+1}}. \]
+\end{slide}
+
+\begin{slide}
+ \head{PRPs are PRFs, \seq: proof (cont.)}
+
+ Game~$\G3$ works in the same way as $\G2$, except that we use a random
+ permutation $P \inr \Perm{L}$ instead of a random function $R \inr
+ \Func{L}{L}$. Firstly, note that $F_2$ can't occur in $\G3$. But, if
+ $F_2$ doesn't occur in $\G2$ (i.e., there is no collision), then the random
+ function is indistinguishable from a random permutation. So
+ \[ \Pr[S_3] = \Pr[S_2]. \]
+
+ By definition, we have
+ \[ \Adv{prp}{F}(A) = \Pr[S_1] - \Pr[S_3]. \]
+ We can now tie all of this together.
+\end{slide}
+
+\begin{slide}
+ \head{PRPs are PRFs, \seq: proof (cont.)}
+
+ A simple calculation shows that