X-Git-Url: https://git.distorted.org.uk/~mdw/doc/ips/blobdiff_plain/41761fdc7bb8f1ed87f5e1116d389158513ee280..6606ff41fcf6918d7aee5d4da006e57dffee35c9:/basics.tex

diff --git a/basics.tex b/basics.tex
index 6d5be48..de5527b 100644
--- a/basics.tex
+++ b/basics.tex
@@ -35,7 +35,7 @@ But if your cryptography is no good, you may never know.
   \topic{serious message}
   \head{Cryptography is elephant powder}
 
-  So, what can we do about the situtation?
+  So, what can we do about the situation?
   \begin{itemize}
   \item Design simple cryptographic primitives, e.g., block ciphers, hash
     functions.  Develop techniques for analysing them, and attempt to stay
@@ -82,7 +82,8 @@ But if your cryptography is no good, you may never know.
 
 \begin{slide}
   \topic{the asymptotic approach}
-  \head{The asymptotic approach, 1}
+  \resetseq
+  \head{The asymptotic approach, \seq}
   
   A function $\nu\colon \N \to \R$ is \emph{negligible} if, for any integer
   $c$, there exists an $n \in \N$ such that $0 \le \nu(k) < k^{-c}$ for all
@@ -97,7 +98,7 @@ But if your cryptography is no good, you may never know.
 \end{slide}
 
 \begin{slide}
-  \head{The asymptotic approach, 2}
+  \head{The asymptotic approach, \seq}
   
   Suppose we build an encryption scheme from a one-way function.  We'd like
   to prove that the encryption is good if the one-way function is secure.  We
@@ -141,7 +142,8 @@ But if your cryptography is no good, you may never know.
 
 \begin{slide}
   \topic{boolean operators}
-  \head{Notation, 1: boolean operators}
+  \resetseq
+  \head{Notation, \seq: boolean operators}
 
   If $P$ and $Q$ are \emph{predicates} -- i.e., either true or false -- then:
   \begin{itemize}
@@ -154,7 +156,7 @@ But if your cryptography is no good, you may never know.
 
 \begin{slide}
   \topic{sets}
-  \head{Notation, 2: sets}
+  \head{Notation, \seq: sets}
 
   For our purposes, we can think of sets as being collections of objects.
   
@@ -162,30 +164,45 @@ But if your cryptography is no good, you may never know.
   \cap Y$), union ($X \cup Y$) and subset containment ($X \subseteq Y$).  The
   \emph{empty set}, which contains no elements, is written $\emptyset$.
   
-  The notation $\{f(x) \mid P(x)\}$ describes the set containing those items
-  $f(x)$ for which the predicate $P(x)$ is true.
+  The notation $\{\, f(x) \mid P(x) \,\}$ describes the set containing those
+  items $f(x)$ for those $x$ for which the predicate $P(x)$ is true.
 
   The \emph{cardinality} $|X|$ of a (finite) set $X$ is the number of
   elements in the set.
   
   The power set $\powerset(X)$ of a set $X$ is the set of all subsets of $X$.
+  
+  The \emph{Cartesian product} of two sets $X \times Y$ is the set of all
+  ordered pairs $\{\, (x, y) \mid x \in X \land y \in Y \,\}$.  We use
+  exponents to indicate the product of a set with itself: hence, $X^2 = X
+  \times X$.
+  
+  A \emph{relation} $R$ is a subset of a Cartesian product.  We write $R(x,
+  y)$ if $(x, y) \in R$.  Relations between two sets are often written as
+  infix symbols: e.g., $x \sim y$.
 \end{slide}
 
 \begin{slide}
-  \head{Notation, 3: sets (cont.)}
-
-  The \emph{cartesian product} of two sets $X \times Y$ is the set of all
-  ordered pairs $\{ (x, y) \mid x \in X \land y \in Y \}$.  We use exponents
-  to indicate the product of a set with itself: hence, $X^2 = X \times X$.
+  \head{Notation, \seq: sets (cont.)}
   
-  A \emph{relation} $R$ is a subset of a cartesian product.  We write $R(x,
-  y)$ if $(x, y) \in R$.  Relations between two sets are often written as
-  infix symbols: e.g., $x \sim y$.
+  In addition to strings, defined later, we use the following standard sets:
+  \begin{itemize}
+  \item the set $\Z$ of integers;
+  \item the set $\N = \{\, x \in \Z \mid x \ge 0 \,\}$ of natural numbers;
+  \item the set $\R$ of real numbers;
+  \item closed intervals $[a, b] = \{\, x \in \R \mid a \le x \le b \,\}$;
+  \item the finite field $\F_q$ of $q$ elements, and its multiplicative
+    subgroup $\F_q^* = \F_q \setminus \{0\}$; and
+  \item the ring $\Z/n\Z$ of residue classes modulo $n$ (i.e., if $x \in
+    \Z/n\Z$ and $a, b \in x$ then $a \equiv b \pmod{n}$), and its
+    multiplicative subgroup $(\Z/n\Z)^* = \Z/n\Z - \{\, x + n\Z \mid \gcd(x,
+    n) > 1 \,\}$.
+  \end{itemize}
 \end{slide}
   
 \begin{slide}
   \topic{functions}
-  \head{Notation, 4: functions}
+  \head{Notation, \seq: functions}
 
   A \emph{function} $f\colon X \to Y$ is a mapping which assigns every
   element $x$ in the \emph{domain} $X$ a corresponding element $f(x)$ in the
@@ -203,10 +220,13 @@ But if your cryptography is no good, you may never know.
   \emph{onto}).  If $f$ is both injective and surjective then we say that it
   is \emph{bijective}.  In this case, there is a well-defined inverse
   $f^{-1}\colon Y \to X$ defined by $f(f^{-1}(y)) = y$ for all $y \in Y$.
+  
+  If $f\colon X \to X$ (i.e., its domain and range are the same set) is
+  bijective, then we say that $f$ is a \emph{permutation on $X$}.
 \end{slide}
 
 \begin{slide}
-  \head{Notation, 5: functions (cont.)}
+  \head{Notation, \seq: functions (cont.)}
 
   We can consider a function $f\colon X \to Y$ to be a particular sort of
   relation $f \subseteq X \times Y$, subject to the constraint that if $(x,
@@ -226,7 +246,7 @@ But if your cryptography is no good, you may never know.
 
 \begin{slide}
   \topic{strings}
-  \head{Notation, 6: strings}
+  \head{Notation, \seq: strings}
   
   An \emph{alphabet} is a finite set of \emph{symbols}.  The one we'll use
   most of the time is the set $\Sigma = \{0, 1\}$ of \emph{bits}.
@@ -234,7 +254,7 @@ But if your cryptography is no good, you may never know.
   Suppose $A$ is an alphabet.  The set of sequences of exactly $n$ symbols
   from $A$ is written $A^n$.  Hence, $\{0, 1\}^{64}$ is the set of all 64-bit
   sequences.  The set of (finite) \emph{strings} over an alphabet $A$ is $A^*
-  = \bigcup_{i \in \N} A^n$.  The empty string is named $\emptystring$.
+  = \bigcup_{i \in \N} A^i$.  The empty string is named $\emptystring$.
   
   The \emph{length} of a string $a \in A^*$, written $|a|$, is the natural
   number $n$ where $a \in A^n$.
@@ -245,9 +265,9 @@ But if your cryptography is no good, you may never know.
 \end{slide}
 
 \begin{slide}
-  \head{Notation, 7: strings (cont.)}
+  \head{Notation, \seq: strings (cont.)}
   
-  There are natural (bijective) mappings between bit strings and natual
+  There are natural (injective) mappings between bit strings and natural
   numbers.
   
   If $x = x_0 x_1 \ldots x_{n-1} \in \{0, 1\}^*$ then we can associate with
@@ -259,12 +279,12 @@ But if your cryptography is no good, you may never know.
   It doesn't matter which you choose, as long as you're consistent.
   
   For simplicity's sake, we shall tend to switch between strings and the
-  numbers (and occasionally more exotic objects) they represent implictly.
+  numbers (and occasionally more exotic objects) they represent implicitly.
 \end{slide}
 
 \begin{slide}
   \topic{parsing}
-  \head{Notation, 8: parsing}
+  \head{Notation, \seq: parsing}
 
   We'll find it useful to be able to break up strings in the algorithms we
   present.  We use the statement
@@ -283,14 +303,14 @@ But if your cryptography is no good, you may never know.
 
 \begin{slide}
   \topic{vectors}
-  \head{Notation, 9: vectors}
+  \head{Notation, \seq: vectors}
   
   A \emph{vector} $\vect{x}$ is a finite ordered collection of elements from
   some set $X$.  If $\vect{x}$ contains $n$ elements then we write $\vect{x}
   \in X^n$, and that $|\vect{x}| = n$.  We write the individual elements as
   $\vect{x}[0], \vect{x}[1], \ldots, \vect{x}[n - 1]$.
 
-  We shall use set membership notation for vectors; i.e., we write $x \in
+  We shall abuse set membership notation for vectors; i.e., we write $x \in
   \vect{x}$ if there is an $i$ ($0 \le i < |\vect{x}|$) such that
   $\vect{x}[i] = x$.
 
@@ -302,7 +322,7 @@ But if your cryptography is no good, you may never know.
 
 \begin{slide}
   \topic{distributions and randomness}
-  \head{Notation, 10: distributions and randomness}
+  \head{Notation, \seq: distributions and randomness}
   
   A \emph{probability distribution} over a (countable) set $X$ is a
   function $\mathcal{D}\colon X \to [0, 1]$ such that
@@ -328,15 +348,17 @@ But if your cryptography is no good, you may never know.
 
 \begin{slide}
   \topic{distinguishability}
-  \head{Distinguishability, 1}
+  \resetseq
+  \head{Distinguishability, \seq}
 
   Suppose that $\mathcal{X}$ and $\mathcal{Y}$ are two probability
   distributions.
-
+  
   Let $X$ be a random variable distributed according to $\mathcal{X}$, and
   let $Y$ be a random variable distributed according to $\mathcal{Y}$.  We
-  say that $\mathcal{A}$ and $\mathcal{B}$ are \emph{identically
-  distributed} if, for all possible values $x$ of $X$, we have
+  say that $\mathcal{X}$ and $\mathcal{Y}$ are \emph{identically
+    distributed}, and write that $\mathcal{X} \equiv \mathcal{Y}$, if, for
+  all possible values $x$ of $X$, we have
   \[ \Pr[X = x] = \Pr[Y = x]. \]
 
   Equivalently, we require that, for all $x \in \supp \mathcal{X}$ we have
@@ -344,43 +366,59 @@ But if your cryptography is no good, you may never know.
 \end{slide}
 
 \begin{slide}
-  \head{Distinguishability, 2: statistical closeness}
+  \head{Distinguishability, \seq: statistical closeness}
   
   Now we generalize the setting slightly.  Consider two \emph{families} of
-  distributions, $\{\mathcal{X}_k\}_{k \in \N}$ and $\{\mathcal{Y}_k\}_{k \in
-    \N}$, parameterized by a security parameter $k$.
+  distributions, $\{\mathcal{X}_k\}_{k\in\N}$ and
+  $\{\mathcal{Y}_k\}_{k\in\N}$, parameterized by a security parameter $k$,
+  where $\dom\mathcal{X}_k = \dom\mathcal{Y}_k$.  To make the asymptotics
+  work, we require that $|x| \le p(k)$ for some polynomial $p(\cdot)$, for
+  all $x \in \dom\mathcal{X}_k$.
   
   Fix a value of $k$.  Again, let $X$ be distributed according to
   $\mathcal{X}_k$, and let $Y$ be distributed according to $\mathcal{Y}_k$.
-  We say that $\{\mathcal{X}_k\}_{k \in \N}$ and $\{\mathcal{Y}_k\}_{k \in
-    \N}$ are \emph{statistically close} if there is a negligible function
-  $\nu(\cdot)$ such that for any $k \in \N$, and for all $x \in
-  \supp \mathcal{X}_k$,
-  \[ |{\Pr[X = x]} - \Pr[Y = x]| \le \nu(k). \]
-  
+  We say that $\{\mathcal{X}_k\}_{k \in \N}$ and $\{\mathcal{Y}_k\}_{k\in\N}$
+  are \emph{statistically close}, and write that $\{\mathcal{X}_k\}_{k\in\N}
+  \statclose \{\mathcal{Y}_k\}_{k\in\N}$, if there is a negligible function
+  $\nu(\cdot)$ such that, for any $k \in \N$,
+  \[ \sum_{x\in\dom{\mathcal{X}_k}}
+     |{\Pr[X = x]} - \Pr[Y = x]| \le \nu(k). \]%
   (Reminder: Saying that $\nu\colon \N \to \R$ is \emph{negligible} means
   that, for any $c \in \Z$ there is an $n \in N$ such that $\nu(k) <
   k^{-c}$.)
 \end{slide}
 
 \begin{slide}
-  \head{Distinguishability, 3: computational indistinguishability}
+  \head{Distinguishability, \seq: computational indistinguishability}
 
   We say that two families of distributions are computationally
   indistinguishable if no `efficient' algorithm can tell them apart with
   better than `negligible' probability.
   
-  So, we say that $\{\mathcal{X}_k\}_{k \in \N}$ and $\{\mathcal{Y}_k\}_{k
-    \in \N}$ are \emph{computationally indistinguishable} if, for any
-  probabilistic polynomial-time algorithm $A$, there is a negligible function
-  $\nu(\cdot)$ such that, for any $k$:
+  So, we say that $\{\mathcal{X}_k\}_{k\in\N}$ and
+  $\{\mathcal{Y}_k\}_{k\in\N}$ are \emph{computationally indistinguishable}
+  and write that $\{\mathcal{X}_k\}_{k\in\N} \compind
+  \{\mathcal{Y}_k\}_{k\in\N}$, if, for any probabilistic polynomial-time
+  algorithm $A$, there is a negligible function $\nu(\cdot)$ such that, for
+  any $k$:
   \[ \Pr[x \getsr \mathcal{X}_k; b \gets A(x) : b = 1] -
-     \Pr[x \getsr \mathcal{Y}_k; b \gets A(x) : b = 1] \le \nu(k). \]%
+     \Pr[y \getsr \mathcal{Y}_k; b \gets A(y) : b = 1] \le \nu(k). \]%
+  Statistical closeness implies computational indistinguishability.
 \end{slide}
 
+\begin{proof}
+  Let two statistically close distributions $\{\mathcal{X}_k\}_{k\in\N}
+  \statclose \{\mathcal{Y}_k\}_{y\in\N}$ be given.  Fix some $k$, and let $Z
+  = \dom\mathcal{X}_k = \dom\mathcal{Y}_k$.  Now note that the adversary's
+  advantage is given by $\sum_{z\in Z} \Pr[b \gets A(z) : b = 1]
+  |\mathcal{X}_k(z) - \mathcal{Y}_k(z)| \le \sum_{z\in Z} |\mathcal{X}_k(z) -
+  \mathcal{Y}_k(z)| \le \nu(k)$.  Hence the two distributions are
+  computationally indistinguishable.
+\end{proof}
+
 \begin{slide}
   \topic{collisions}
-  \head{Collisions}
+  \head{Collisions -- the Birthday `paradox'}
   
   Suppose we throw $q$ balls into $n$ bins at random (with $q \le n$).  Let
   $C_{q, n}$ be the event that, at the end of this, we have a bin containing
@@ -394,8 +432,8 @@ But if your cryptography is no good, you may never know.
   \begin{eqnarray*}[rl]
     \Pr[C_{q, n}]
     &\le \Pr[B_{2, n}] + \Pr[B_{3, n}] + \cdots + \Pr[B_{q, n}] \\
-    &= \frac{1}{n} + \frac{2}{n} + \cdots + \frac{q - 1}{n} \\
-    &= \frac{q(q - 1)}{2 n}.
+    &\le \frac{1}{n} + \frac{2}{n} + \cdots + \frac{q - 1}{n} \\
+    &=   \frac{q(q - 1)}{2 n}.
   \end{eqnarray*}
   This is an extremely useful result, and we shall need it often.
 \end{slide}
@@ -404,7 +442,8 @@ But if your cryptography is no good, you may never know.
 
 \begin{slide}
   \topic{one-way functions}
-  \head{One-way functions, 1: introduction}
+  \resetseq
+  \head{One-way functions, \seq: introduction}
 
   Intuition: a one-way function is easy to compute but hard to invert.
 
@@ -421,7 +460,7 @@ But if your cryptography is no good, you may never know.
 \end{slide}
 
 \begin{slide}
-  \head{One-way functions, 2: formalism}
+  \head{One-way functions, \seq: formalism}
 
   The \emph{success probability} of an inverter $I$ against the function $f$
   is
@@ -443,11 +482,12 @@ But if your cryptography is no good, you may never know.
 \end{slide}
 
 \begin{slide}
-  \head{One-way functions, 3: trapdoors}
+  \head{One-way functions, \seq: trapdoors}
   
   Intuition: a \emph{trapdoor} is secret information which makes inverting a
-  one-way function easy.  A trapdoor one-way function generator $\mathcal{T}
-  = (G, f, T)$ is a triple of algorithms:
+  one-way function easy.  This is most useful when the one-way function is a
+  permutation.  A trapdoor one-way function generator $\mathcal{T} = (G, f,
+  T)$ is a triple of algorithms:
 
   \begin{itemize}
   \item The probabilistic algorithm $G$ is given some parameter $k$ and
@@ -460,8 +500,8 @@ But if your cryptography is no good, you may never know.
     one-way function.
     
   \item The algorithm $T$ inverts $f$ using the trapdoor information.  That
-    is, if $(P, K) \in G(k)$ and $y = f_P(x)$ for some $x$, then $x =
-    T(K, y)$.  We usually write $T_K(\cdot)$ instead of $T(K, \cdot)$.
+    is, if $(P, K) \in G(k)$ and $y = f_P(x)$ for some $x$, then $y =
+    f_P(T(K, y))$.  We usually write $T_K(\cdot)$ instead of $T(K, \cdot)$.
   \end{itemize}
 \end{slide}
 
@@ -520,6 +560,9 @@ But if your cryptography is no good, you may never know.
      g^{(i+1)}(x) = g_0(x) \cat g^{(i)}(g_1(x)). \]%
   Relate the security of $g^{(i)}$ to that of $g$.
   \answer%
+  The description of the function $g^{(i)}$ is deliberately terse and
+  unhelpful.  It probably helps understanding if you make a diagram.
+
   Let $A$ be an adversary running in time $t$ and attacking $g^{(i+1)}$.
   Firstly, we attack $g$: consider adversary $B(y)$: \{ \PARSE $y$ \AS $y_0,
   k\colon y_1$; $z \gets g^{(i)}$; $b \gets A(y_0 \cat z)$; \RETURN $b$;~\}.
@@ -599,7 +642,9 @@ But if your cryptography is no good, you may never know.
   
   A \emph{pseudorandom function family} (PRF) is a collection of functions
   $F_K\colon \{0, 1\}^l \to \{0, 1\}^L$, where $K$ is some index, typically
-  from a set of fixed-size strings $\{0, 1\}^k$.
+  from a set of fixed-size strings $\{0, 1\}^k$.  We shall often consider a
+  PRF to be a single function $F\colon \{0, 1\}^k \times \{0, 1\}^l \to \{0,
+  1\}^L$.
 
   We want to say that $F$ is a strong PRF if adversaries find it hard to
   distinguish an instance $F_K$ from a function chosen completely at random
@@ -614,7 +659,7 @@ But if your cryptography is no good, you may never know.
 \end{slide}
 
 \begin{slide}
-  \head{Pseudorandomness, 3: PRFs (cont.)}
+  \head{Pseudorandom functions (cont.)}
 
   We define the advantage of a distinguisher $D$ against the PRF $F$ as
   follows:
@@ -633,12 +678,15 @@ But if your cryptography is no good, you may never know.
 \begin{slide}
   \topic{pseudorandom permutations (PRPs)}
   \head{Pseudorandom permutations (PRPs)}
-
+  
   We define a \emph{pseudorandom permutation family} (PRP) in a similar way
-  to the PRFs we've already seen.  Suppose $F_K\colon \{0, 1\}^L \to \{0,
-  1\}^L$ is a family of permutations, indexed by elements of some finite set,
-  e.g., $\{0, 1\}^k$.  Let $\Perm{L}$ be the set of \emph{all} permutations
-  over the set of $L$-bit strings $\{0, 1\}^L$.
+  to the PRFs we've already seen.  A PRP is a family $F_K\colon \{0, 1\}^L
+  \to \{0, 1\}^L$ is a of permutations, indexed by elements of some finite
+  set, e.g., $\{0, 1\}^k$.  We shall often consider a PRP to be a single
+  function $F\colon \{0, 1\}^k \times \{0, 1\}^l \to \{0, 1\}^L$.
+  
+  Let $\Perm{L}$ be the set of \emph{all} permutations over the set of
+  $L$-bit strings $\{0, 1\}^L$.
 
   The advantage of a distinguisher $D$ against the PRP $F$ is
   \begin{eqnarray*}[rl]
@@ -652,14 +700,13 @@ But if your cryptography is no good, you may never know.
 \end{slide}
 
 \begin{slide}
-  \head{Pseudorandomness, 5: super PRPs}
+  \head{Super pseudorandom permutations}
   
   PRPs are bijective.  A \emph{super PRP} is a PRP which remains secure when
   the distinguisher is allowed to make inverse queries:
   \begin{eqnarray*}[rl]
     \Adv{sprp}{F}(D) = &
-      \Pr[D^{F_K(\cdot), F_K^{-1}(\cdot)} = 1 \mid
-          K \getsr \{0, 1\}^k] - {} \\
+      \Pr[K \getsr \{0, 1\}^k : D^{F_K(\cdot), F_K^{-1}(\cdot)} = 1] - {} \\
     & \Pr[R \getsr \Perm{L} : D^{R(\cdot), R^{-1}(\cdot)} = 1].
   \end{eqnarray*}
   Since there are two oracles, we count queries to both when evaluating the
@@ -685,7 +732,8 @@ But if your cryptography is no good, you may never know.
 \end{exercise}
 
 \begin{slide}
-  \head{Block ciphers: PRPs are PRFs}
+  \resetseq
+  \head{PRPs are PRFs, \seq}
 
   We model block ciphers as families of PRPs (not super PRPs).  Most of the
   analysis works best on PRFs, though.  We show that a PRP makes a `pretty
@@ -697,48 +745,130 @@ But if your cryptography is no good, you may never know.
   This is a useful result.  As long as $q^2$ is small compared to $2^L$ --
   the block size -- then a PRP makes a good PRF.
   
-  The value $2^{L/2}$ is often called the \emph{Birthday bound} (after the
-  birthday `paradox').  We shall meet it often when we examine modes of
-  operation.
+  The value $2^{L/2}$ is often called the \emph{Birthday bound}.  We shall
+  meet it often when we examine modes of operation.  We shall examine the
+  proof, because it illustrates some useful techniques.
 \end{slide}
 
-\begin{proof}
-  Let $F$ be a PRP family, and $K$ a randomly chosen key from the keyspace of
-  $F$; let $R \inr \Func{L}{L}$ be a random function, and let $P \inr
-  \Perm{L}$ be a random permutation.
+\begin{slide}
+  \head{Shoup's lemma}
+  
+  This handy lemma states that the difference in the probability of some
+  outcome between the two games is bounded above by the probability that the
+  games differ.
+
+  \begin{lemma}[Shoup \cite{Shoup:2001:OAEPR}]
+    \label{lem:shoup}
+    If $X$, $Y$ and $F$ are events, and $\Pr[X \land \lnot F] = \Pr[Y \land
+    \lnot F]$ then $|{\Pr[X]} - \Pr[Y]| \le \Pr[F]$.
+  \end{lemma}
+  \begin{proof}
+    We have:
+    \begin{eqnarray*}[rll]
+      \Pr[X] &= \Pr[X \land F] &+ \Pr[X \land \lnot F] \\
+      \Pr[Y] &= \Pr[Y \land F] &+ \Pr[Y \land \lnot F]
+    \end{eqnarray*}
+    Subtracting gives
+    \[ |{\Pr[X]} - \Pr[Y]| = |{\Pr[X \land F]} -
+       \Pr[Y \land F]| \le \Pr[F] \]%
+    as required.
+  \end{proof}
+\end{slide}
+
+\begin{slide}
+  \head{PRPs are PRFs, \seq: proof}
+
+  Let $F\colon \{0, 1\}^k \times \{0, 1\}^L \to \{0, 1\}^L$ be a pseudorandom
+  permutation.  We aim to show that $F$ is also a pseudorandom function.
   
-  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
   \begin{eqnarray*}[rl]
-    \Pr[A^{R(\cdot)} = 0]
-    & = \Pr[A^{R(\cdot)} = 0 \mid D] \Pr[D] +
-        \Pr[A^{R(\cdot)} = 0 \mid \lnot D] \Pr[\lnot D] \\
-    & = \Pr[A^{P(\cdot)} = 0] \Pr[D] +
-        \Pr[A^{R(\cdot)} = 0 \mid \lnot D] \Pr[\lnot D] \\
-    & \le \Pr[A^{P(\cdot)} = 0] + \Pr[\lnot D] \\
-    & \le \Pr[A^{P(\cdot)} = 0] + \frac{q(q - 1)}{2^{L+1}}.
+    \Adv{prf}{F}(A) &=   \Pr[S_1] - \Pr[S_0] \\
+                    &\le \Pr[S_1] - \Pr[S_2] + \Pr[F_2] \\
+                    &=   \Pr[S_1] - \Pr[S_3] + \Pr[F_2] \\
+                    &=   \Adv{prp}{F}(A) + \Pr[F_2] \\
+                    &\le \InSec{prp}(F; t, q) + \frac{q(q - 1)}{2^{L+1}}.
   \end{eqnarray*}
-  Substituting this into the above equation yields
-  \[ \Adv{prf}{F}(A) \le \Adv{prp}{F}(A) + \frac{q(q - 1)}{2^{L+1}}. \]
-  Select $A$ such that $\Adv{prf}{F}(A) = \InSec{prf}(F; t, q)$.  We know
-  $\Adv{prp}{F}(A) \le \InSec{prp}(F; t, q)$ by definition.  The result
-  follows.
-\end{proof}
+  In the second line, we used the bound we computed on the absolute
+  difference between $\Pr[S_2]$ and $\Pr[S_0]$; in the third, we noted that
+  $\Pr[S_2] = \Pr[S_3]$; in the fourth, we used the definition of advantage
+  against a PRP; and in the fifth we used the definition of insecurity for a
+  PRP.
+\end{slide}
+
+\begin{slide}
+  \head{PRPs are PRFs, \seq: proof (cont.)}
+
+  Finally, we imposed no restrictions on $A$, except that it run in time $t$
+  and make $q$ oracle queries.  So our bound
+  \[ \Adv{prf}{F}(A) \le \InSec{prp}(F; t, q) + \frac{q(q - 1)}{2^{L+1}} \]%
+  is true for \emph{any} such adversary $A$, and in particular, it's true for
+  the most successful adversary running with those resource bounds.
+
+  Hence, we can maximize, showing that
+  \[ \InSec{prf}(F; t, q) \le
+     \InSec{prp}(F; t, q) + \frac{q(q - 1)}{2^{L+1}} \]%
+  as required.
+\end{slide}
 
 \begin{slide}
   \topic{hash functions}
-  \head{Hash functions, 1: properties}
+  \resetseq
+  \head{Hash functions, \seq: properties}
 
   Hash functions like MD5 and SHA-1 are extremely useful primitives.  What
   properties do we expect of them?  This out to be an extremely difficult
@@ -755,7 +885,7 @@ But if your cryptography is no good, you may never know.
 \end{slide}
   
 \begin{slide}
-  \head{Hash functions, 2: Merkle-Damg\aa{}rd iterated hashing
+  \head{Hash functions, \seq: Merkle-Damg\aa{}rd iterated hashing
     \cite{Damgaard:1990:DPH, Merkle:1991:FSE}}
   
   Let $F\colon \{0, 1\}^{k+L} \to \{0, 1\}^k$ be a \emph{compression}
@@ -764,7 +894,7 @@ But if your cryptography is no good, you may never know.
   \begin{enumerate}
   \item Pad $x$ to a multiple of $L$ bits in some injective way.  Divide the
     padded message into $L$-bit blocks $x_0$, $x_1$, \ldots, $x_{n-1}$.
-  \item Fix some $L$-bit constant $I$.  Let $I_0 = I$.  Define $I_{i+1} =
+  \item Fix some $k$-bit constant $I$.  Let $I_0 = I$.  Define $I_{i+1} =
     F(I_i \cat x_i)$ for $0 \le i < n$.
   \item The result $H(x) = I_n$.
   \end{enumerate}
@@ -795,7 +925,24 @@ But if your cryptography is no good, you may never know.
 \end{proof}
 
 \begin{slide}
-  \head{Hash functions, 2: any-collision resistance}
+  \head{Hash functions, \seq: Merkle-Damg\aa{}rd iterated hashing (cont.)}
+
+  \vfil
+  \[ \begin{graph}
+    []!{0; <2cm, 0cm>: <0cm, 0.9cm>::}
+    *+=(1, 0)+[F]{\mathstrut I_0 = I} :[d] *+[F]{F}="f"
+    [urrr] *+=(3, 0)+[F]{\mathstrut x_0} :`d"f" "f" :[d]
+    *+=(1, 0)+[F]{\mathstrut I_1} :[d] *+[F]{F}="f"
+    [urrr] *+=(3, 0)+[F]{\mathstrut x_1} :`d"f" "f" :@{-->}[dd]
+    *+=(1, 0)+[F]{\mathstrut I_{n-1}} :[d] *+[F]{F}="f"
+    [urrr] *+=(3, 0)+[F]{\mathstrut x_{n-1}} :`d"f" "f" :[d]
+    *+=(1, 0)+[F:thicker]{\mathstrut H(x) = I_n}
+  \end{graph} \]
+  \vfil
+\end{slide}
+
+\begin{slide}
+  \head{Hash functions, \seq: any-collision resistance}
   
   The statement usually made about a `good' hash function $h$ is that it
   should be `difficult' to find a collision: i.e., two preimages $x \ne y$
@@ -811,7 +958,7 @@ But if your cryptography is no good, you may never know.
 \end{slide}
 
 \begin{slide}
-  \head{Hash functions, 3: targetted collision resistance}
+  \head{Hash functions, \seq: targetted collision resistance}
 
   The concept of targetted collision resistance is relatively new, but quite
   promising.  It replaces a single hash function with a \emph{family} of hash
@@ -826,7 +973,7 @@ But if your cryptography is no good, you may never know.
 \end{slide}
 
 \begin{slide}
-  \head{Hash functions, 4: targetted collision resistance (cont.)}
+  \head{Hash functions, \seq: targetted collision resistance (cont.)}
 
   Consider the following experiment:
   \begin{program}
@@ -845,7 +992,7 @@ But if your cryptography is no good, you may never know.
 \end{slide}
 
 \begin{slide}
-  \head{Hash functions, 5: random oracles \cite{Bellare:1993:ROP}}
+  \head{Hash functions, \seq: random oracles \cite{Bellare:1993:ROP}}
 
   In practice, we expect much more than just collision resistance from hash
   functions: we expect a certain amount of `random' behaviour.  But this is
@@ -880,7 +1027,8 @@ But if your cryptography is no good, you may never know.
 
 \begin{slide}
   \topic{integer factorization}
-  \head{The Integer Factorization Problem, 1}
+  \resetseq
+  \head{The Integer Factorization Problem, \seq}
     
   We often assume that large integers of the form $n = p q$, where $p$ and
   $q$ are primes of roughly the same size, are `hard' to factor.
@@ -893,7 +1041,7 @@ But if your cryptography is no good, you may never know.
 \end{slide}
 
 \begin{slide}
-  \head{The Integer Factorization Problem, 2: square roots}
+  \head{The Integer Factorization Problem, \seq: square roots}
   
   The problem of extracting square roots modulo $n = p q$ is provably as hard
   as factoring.  This is the basis of Rabin's public key encryption and
@@ -976,7 +1124,10 @@ But if your cryptography is no good, you may never know.
   
   If $n = p q$ is a product of two primes and $x \inr (\Z/n\Z)^*$ is chosen
   at random, then
-  \[ \Pr\Bigl[x \in Q_n \Bigm| \jacobi{x}{n} = 1\Bigr] = \frac{1}{2}. \]
+  \[ \Pr\Bigl[x \in Q_n \Bigm| \jacobi{x}{n} = 1\Bigr] = \frac{1}{2}, \]
+  since we have
+  \[ \jacobi{x}{p} = \jacobi{x}{q} = \pm 1 \]
+  with each occurring with equal probability.
 
   The problem of distinguishing pseudosquares from quadratic residues is
   called the Quadratic Residuosity Problem (QRP).  It is not known how to
@@ -999,7 +1150,8 @@ But if your cryptography is no good, you may never know.
 
 \begin{slide}
   \topic{self-reducibility}
-  \head{Self-reducibility, 1}
+  \resetseq
+  \head{Self-reducibility, \seq}
   
   The problems of square-root extraction, deciding quadratic residuosity, the
   RSA problem, and finding discrete logarithms share the property of being
@@ -1013,13 +1165,13 @@ But if your cryptography is no good, you may never know.
 \end{slide}
 
 \begin{slide}
-  \head{Self-reducibility, 2: the RSA problem \cite{Rivest:1978:MOD}}
+  \head{Self-reducibility, \seq: the RSA problem \cite{Rivest:1978:MOD}}
   
   The RSA problem is to compute $e$-th roots modulo $n = p q$, where $e$ is
   relatively prime to $n$.  Suppose that the algorithm $S(n, e, y)$ returns a
   value $x$ such that $x^e \equiv y \pmod{n}$ for `many' choices of $y$, or
   the special symbol $\bot$ otherwise.  The following probabilistic algorithm
-  then solves the RSA problem for arbitary $y$:
+  then solves the RSA problem for arbitrary $y$:
   \begin{program}
     Algorithm $\id{solve-rsa}(n, e, y)$: \+ \\
       \REPEAT \\ \quad\=\+\kill
@@ -1044,7 +1196,7 @@ But if your cryptography is no good, you may never know.
   
   The (computational) Diffie-Hellman \emph{assumption} is that there is no
   probabilistic algorithm which solves the computational Diffie-Hellman
-  problem in time polynomial in $q$.
+  problem in time polynomial in $\log q$.
   
   Obviously, being able to compute discrete logs in $G$ efficiently would
   yield a solution to the Diffie-Hellman problem.  But it may be the case
