From 53aa10b5d9431ced4e98673cc872c6627cac1d5f Mon Sep 17 00:00:00 2001
From: mdw <mdw>
Date: Fri, 12 Oct 2001 18:55:28 +0000
Subject: [PATCH] Fix typos.  Replace proof that PRPs are PRFs.  Other fixes.

---
 auth-mac.tex  | 126 ++++++++++++++-------
 auth-sig.tex  |  10 +-
 basics.tex    | 357 +++++++++++++++++++++++++++++++++++++++-------------------
 enc-ies.tex   |  11 +-
 enc-intro.tex |  13 +--
 enc-pub.tex   |  44 ++------
 enc-symm.tex  |  31 ++---
 ips.cls       |   5 +
 8 files changed, 377 insertions(+), 220 deletions(-)

diff --git a/auth-mac.tex b/auth-mac.tex
index 0c3e6e5..8b4eb8a 100644
--- a/auth-mac.tex
+++ b/auth-mac.tex
@@ -21,7 +21,8 @@
 
 \begin{slide}
   \topic{informal security notion}
-  \head{Strong MACs, 1: informal security notion}
+  \resetseq
+  \head{Strong MACs, \seq: informal security notion}
   
   Our standard notion of security for MACs is \emph{strong unforgeability
     against chosen message attack}, or SUF-CMA, for short
@@ -41,7 +42,7 @@
 
 \begin{slide}
   \topic{strong MACs}
-  \head{Strong MACs, 2: the experiment}
+  \head{Strong MACs, \seq: the experiment}
 
   We perform the following experiment with the adversary.
   \begin{program}
@@ -60,7 +61,7 @@
 \end{slide}
 
 \begin{slide}
-  \head{Strong MACs, 3: wrapping up the notation}
+  \head{Strong MACs, \seq: wrapping up the notation}
 
   The \emph{success probability} of an adversary $A$ against the MAC
   $\mathcal{M}$ in the sense of SUF-CMA is
@@ -101,7 +102,8 @@
 
 \begin{slide}
   \topic{PRFs are MACs}
-  \head{PRFs are MACs, 1}
+  \resetseq
+  \head{PRFs are MACs, \seq}
   
   If $F_K\colon \{0, 1\}^* \to \{0, 1\}^L$ is a $(t, q, \epsilon)$-secure
   PRF, then it's also a $(t', q_T, q_V, \epsilon')$-secure MAC, with $q = q_T
@@ -118,7 +120,7 @@
 \end{slide}
 
 \begin{slide}
-  \head{PRFs are MACs, 2: the distinguisher}
+  \head{PRFs are MACs, \seq: the distinguisher}
 
   \begin{program}
     Distinguisher $D^{F(\cdot)}$: \+ \\
@@ -137,7 +139,7 @@
 \end{slide}
 
 \begin{slide}
-  \head{PRFs are MACs, 3: wrapping up}
+  \head{PRFs are MACs, \seq: wrapping up}
 
   The distinguisher simulates the tagging and verification oracles for the
   MAC forger, using its supplied oracle.  If the forger succeeds, then the
@@ -156,12 +158,44 @@
      \InSec{prf}(F; t + O(q), q) + (q_V + 1)2^{-L}. \]%
 \end{slide}
 
+\begin{slide}
+  \head{PRFs are MACs, \seq: MACs aren't PRFs}
+  
+  The converse of our result is not true.  Suppose $\mathcal{M} = (T, V)$ is
+  a deterministic MAC.  Choose some integer $n$.  Then define $\mathcal{M}' =
+  (T', V')$, as follows:
+  \[ T'_K(x) = 0^n \cat T_K(x); \qquad
+     V'_K(x, \tau) = \begin{cases}
+       1 & if $T'_K(x) = \tau$ \\
+       0 & otherwise
+     \end{cases}.
+  \]
+  $T'$ is obviously not a PRF: an adversary checking for the string of $n$
+  zero bits on the output will succeed with advantage $1 - 2^{-qn}$.
+  
+  However, $\mathcal{M}'$ is a secure MAC.  Suppose $A'$ attacks
+  $\mathcal{M}'$.
+  \begin{program}
+    Adversary $A^{T(\cdot), V(\cdot)}$: \+ \\
+      $(m, \tau') \gets A'^{\id{tag}(\cdot), \id{verify}(\cdot)}$; \\
+      \PARSE $\tau'$ \AS $n\colon z, \tau$; \\
+      \RETURN $(m, \tau)$;
+  \next
+    Oracle $\id{tag}(m)$: \+ \\
+      \RETURN $0^n \cat T(m)$; \- \\[\smallskipamount]
+    Oracle $\id{verify}(m, \tau')$: \+ \\
+      \PARSE $\tau'$ \AS $n\colon z, \tau$; \\
+      \IF $z \ne 0^n$ \THEN \RETURN $0$; \\
+      \ELSE \RETURN $V(m, \tau)$;
+  \end{program}
+\end{slide}
+
 \begin{exercise}
   \begin{parenum}
   \item Suppose that $F\colon \{0, 1\}^k \times \{0, 1\}^* \to \{0, 1\}^L$ is
     a $(t, q, \epsilon)$-secure PRF.  Let $T^{(\ell)}_K(x)$ be the leftmost
-    $\ell$~bits of $F_K(x)$.  Demonstrate the security of $T^{(\ell)}(\cdot)$
-    as a MAC.
+    $\ell$~bits of $F_K(x)$ for $\ell \le L$.  Demonstrate the security of
+    $T^{(\ell)}(\cdot)$ as a MAC.
   \item Discuss the merits of truncating MAC tags in practical situations.
   \end{parenum}
   \answer%
@@ -232,7 +266,7 @@
     to the tagging oracle.
   \item Once a verification query succeeds, all subsequent verification
     queries also succeed and the adversary returns a correct forgery (e.g.,
-    by simply repeating the succeessful query).
+    by simply repeating the successful query).
   \end{itemize}
   It's clear that any adversary can be transformed into one which has these
   properties and succeeds with probability at least as high.
@@ -292,7 +326,7 @@
   return it; otherwise we guess randomly from the remaining $2^L - q$
   possibilities.  Now
   \begin{eqnarray*}[rl]
-    e_q &= e_{q-1} + (1 - e_{q-1}) \frac{1}{2^L - q} \\
+    e_q &= e_{q-1} + \frac{1 - e_{q-1}}{2^L - q} \\
         &= \frac{q}{2^L} + \frac{2^L - q}{2^L} \cdot \frac{1}{2^L - q} \\
         &= \frac{q + 1}{2^L}
   \end{eqnarray*}
@@ -302,14 +336,20 @@
 \xcalways\subsection{The HMAC construction}\x
 
 \begin{slide}
-  \head{The HMAC construction \cite{Bellare:1996:KHF}, 1: motivation}
-
+  \resetseq
+  \head{The HMAC construction \cite{Bellare:1996:KHF}, \seq: motivation}
+  
   It ought to be possible to construct a decent MAC using a hash function.
   Many attempts have failed, however.  For example, these constructions are
-  weak if used with Merkle-Damg\aa{}rd iterated hashes:
+  weak if used with standard one-pass Merkle-Damg\aa{}rd iterated hashes.
   \begin{itemize}
-  \item Secret prefix: $T_K(m) = H(K \cat m)$.
-  \item Secret suffix: $T_K(m) = H(m \cat K)$.
+  \item Secret prefix: $T_K(m) = H(K \cat m)$.  Given $H(K \cat m)$, it's
+    easy to compute $H(K \cat m \cat p \cat m')$ for a padding string $p$ and
+    arbitrary suffix $m'$.
+  \item Secret suffix: $T_K(m) = H(m \cat K)$.  Finding a collision $H(m) =
+    H(m')$ yields $H(m \cat K) = H(m' \cat K)$.  We saw earlier that
+    adversaries which know collisions \emph{exist} even if we don't know how
+    to describe them.
   \end{itemize}
 
   It would be nice to have a construction whose security was provably related
@@ -317,7 +357,7 @@
 \end{slide}
 
 \begin{slide}
-  \head{The HMAC construction, 2: definition of NMAC}
+  \head{The HMAC construction, \seq: definition of NMAC}
  
   Let $H\colon \{0, 1\}^* \to \{0, 1\}^k$ be an iterated hash, constructed
   from the compression function $F\colon \{0, 1\}^k \times \{0, 1\}^L \to
@@ -337,7 +377,7 @@
 \end{slide}
 
 \begin{slide}
-  \head{The HMAC construction, 3: security of NMAC}
+  \head{The HMAC construction, \seq: security of NMAC}
 
   Consider a function $F\colon \{0, 1\}^k \times \{0, 1\}^* \to \{0, 1\}^k$.
   We say that $F$ is \emph{$(t, q, \epsilon)$-weakly collision resistant} if,
@@ -353,7 +393,7 @@
 \end{slide}
 
 \begin{slide}
-  \head{The HMAC construction, 4: NMAC security proof}
+  \head{The HMAC construction, \seq: NMAC security proof}
 
   Let $A$ be an adversary which forges a $\Xid{T}{NMAC}^H$ tag in time $t$,
   using $q_T$ tagging queries and $q_V$ verification queries with probability
@@ -373,7 +413,7 @@
 \end{slide}
 
 \begin{slide}
-  \head{The HMAC construction, 5: from NMAC to HMAC}
+  \head{The HMAC construction, \seq: from NMAC to HMAC}
 
   Implementing NMAC involves using strange initialization vectors and
   generally messing about with your hash function.  HMAC is an attempt to
@@ -391,7 +431,7 @@
 \end{slide}
 
 \begin{slide}
-  \head{The HMAC construction, 6: comparison with NMAC}
+  \head{The HMAC construction, \seq: comparison with NMAC}
 
   Comparing the two constructions, we see that
   \[ \Xid{T}{HMAC}^H_K =
@@ -424,11 +464,11 @@
   $i \in \{0, 1\}$) using the $H_K$ construction.  Verification in each
   case consists of computing the tag and comparing to the one offered.
   \begin{eqlines*}
-    T^0_K(x) = H_K(x); \qquad T^1_K(x) = H_K(x \cat K)
+    T^0_K(x) = H_K(x); \qquad T^1_K(x) = H_K(x \cat K); \\
     V^i_K(x, \tau) = \begin{cases}
       1 & if $\tau = T^i_K(x)$ \\
       0 & otherwise
-    \end{cases}
+    \end{cases}.
   \end{eqlines*}
   Decide whether each of these constructions is secure.  A full proof is
   rather hard: an informal justification would be good.
@@ -461,7 +501,7 @@
 
   The former is trickier.  This needs a lot more work to make it really
   rigorous, but we show the idea.  Assume that the bad event has not
-  occured. Consider a query $x_0, x_1, \ldots, x_{n-1}$.  If it's the
+  occurred. Consider a query $x_0, x_1, \ldots, x_{n-1}$.  If it's the
   same as an earlier query, then $A$ learns nothing (because it could
   have remembered the answer from last time).  If it's \emph{not} a
   prefix of some previous query, then we must add a new edge to our
@@ -511,7 +551,7 @@
   as $\G1$, except that if $A$ makes any query of the form $p \cat K
   \cat q$ with $|p| = t$ and $|q| = \ell - k$ then the game halts
   immediately, and let $F_2$ be the event that this occurs.  By
-  Lemma~\ref{lem:shoup} (page~\pageref{lem:shoup}), then, $|{\Pr[S_2]} -
+  Lemma~\ref{lem:shoup} (slide~\pageref{lem:shoup}), then, $|{\Pr[S_2]} -
   \Pr[S_1]| \le \Pr[F_2]$.  Let game~$\G3$ be the same as $\G2$ except
   that we give $A$ an oracle for $F_K$ rather than $F'_K$.  Since $F$
   and $F'$ differ only on queries of the form $p \cat K \cat q$, we have
@@ -526,7 +566,7 @@
   as $p \cat K' \cat q$ with $|p| = t$, $|K'| = k$ and $|q| = \ell - k$;
   then, if $F_{K'}(0) = F(0) \land F_{K'}(1) = F(1) \land \cdots \land
   F_{K'}(n - 1) = F(n - 1)$, $B$ immediately returns $1$, claiming that
-  its oracle $F$ is the function $F_{K'}$; if this never occirs, $B$
+  its oracle $F$ is the function $F_{K'}$; if this never occurs, $B$
   returns $0$.  Clearly, if $B$ is given an instance $F_K$ of $F$ then
   it succeeds with probability $\Pr[F_2]$; however, if $F$ is a random
   function then $B$ returns $1$ with probability at most $q 2^{-nk}$.
@@ -534,14 +574,15 @@
   queries, and takes time $t + O(n q)$.  Wrapping everything up, we get
   \[ \InSec{prf}(F'; t, q) \le 
      2\cdot\InSec{prf}(F; t + O(q n), q + n) + \frac{q}{2^{nk}}. \]%
-  This completes the proof of generic insecurty for $\mathcal{M}^1$.
+  This completes the proof of generic insecurity for $\mathcal{M}^1$.
 \end{exercise}
 
 \xcalways\subsection{Universal hashing}\x
 
 \begin{slide}
   \topic{almost-universal hash functions}
-  \head{Universal hashing, 1: definition}
+  \resetseq
+  \head{Universal hashing, \seq: definition}
   
   Consider a family of hash functions $H\colon \keys H \times \dom H \to
   \ran H$.  We define
@@ -571,7 +612,7 @@
 
 \begin{slide}
   \topic{dynamic view}
-  \head{Universal hashing, 2: a dynamic view}
+  \head{Universal hashing, \seq: a dynamic view}
   
   Suppose that $H$ is $\epsilon$-almost universal.  Consider this experiment:
   \begin{program}
@@ -592,7 +633,7 @@
 \end{slide}
 
 \begin{slide}
-  \head{Universal hashing, 3: the dynamic view (cont.)}
+  \head{Universal hashing, \seq: the dynamic view (cont.)}
   
   Now we treat $\rho$ as a random variable, selected from some distribution
   $P$ on the set $\{0, 1\}^*$.  We see that
@@ -611,7 +652,7 @@
 
 \begin{slide}
   \topic{composition}
-  \head{Universal hashing, 4: composition}
+  \head{Universal hashing, \seq: composition}
   
   Suppose that $G$ is $\epsilon$-almost universal, and $G'$ is
   $\epsilon'$-almost universal, and $\dom G = \ran G'$.  We define the
@@ -633,14 +674,14 @@
 
 \begin{slide}
   \topic{the collision game}
-  \head{Universal hashing, 5: the collision game}
+  \head{Universal hashing, \seq: the collision game}
   
   Suppose that, instead of merely a pair $(x, y)$, our adversary was allowed
   to return a \emph{set} $Y$ of $q$ elements, and measure the probability
   that $H_K(x) = H_K(y)$ for some $x \ne y$ with $x, y \in Y$, and for $K
   \inr \keys H$.
   
-  Let $\InSec{uh-set}(H; q)$ be maximum probability acheivable for sets $Y$
+  Let $\InSec{uh-set}(H; q)$ be maximum probability achievable for sets $Y$
   with $|Y| \le q$.  Then
   \[ \InSec{uh-set}(H; q) \le \frac{q(q - 1)}{2} \cdot \InSec{uh}(H) .\]
 \end{slide}
@@ -657,7 +698,7 @@
   The worst that can happen is that $A'$ accidentally removes the one
   colliding element from $Y$.  This occurs with probability $2/q$.  So
   \[ \Succ{uh-set}{H}(A') \ge \frac{q - 2}{q} \Succ{uh-set}{H}(A). \]
-  Rearranging and maximzing gives
+  Rearranging and maximizing gives
   \[ \InSec{uh-set}(H; q) \le
      \frac{q}{q - 2} \cdot \InSec{uh-set}(H; q - 1). \]
   Note that $\InSec{uh-set}(H; 2) = \InSec{uh}(H)$ is our initial notion.  A
@@ -666,10 +707,10 @@
 
 \begin{slide}
   \topic{a MAC}
-  \head{Universal hashing, 6: a MAC}
+  \head{Universal hashing, \seq: a MAC}
   
-  Suppse that $H\colon \{0, 1\}^k \times \{0, 1\}^* \to \{0, 1\}^l$ is an
-  almost universal hash fucntion, and $F\colon \{0, 1\}^{k'} \times \{0,
+  Suppose that $H\colon \{0, 1\}^k \times \{0, 1\}^* \to \{0, 1\}^l$ is an
+  almost universal hash function, and $F\colon \{0, 1\}^{k'} \times \{0,
   1\}^l \to \{0, 1\}^L$ is a PRF\@.  Define a MAC $\Xid{\mathcal{M}}{UH}^{H,
     F} = (\Xid{T}{UH}^{H, F}, \Xid{V}{UH}^{H, F})$ where:
   \begin{eqnarray*}[rl]
@@ -736,7 +777,8 @@
 
 \begin{slide}
   \topic{almost XOR-universality}
-  \head{Almost XOR-universality, 1: definition}
+  \resetseq
+  \head{Almost XOR-universality, \seq: definition}
   
   Consider a family of hash functions $H\colon \keys H \times \dom H \to
   \{0, 1\}^L$.  Define
@@ -756,7 +798,7 @@
   technique as for almost universal functions.
   
   If $H$ is $2^{-L}$-almost XOR universal then we say that $H$ is
-  \emph{XOR-universal}.  This is the best acheivable.
+  \emph{XOR-universal}.  This is the best achievable.
 \end{slide}
 
 \begin{proof}
@@ -778,7 +820,7 @@
 
 \begin{slide}
   \topic{composition}
-  \head{Almost XOR-universality, 2: composition}
+  \head{Almost XOR-universality, \seq: composition}
   
   We extend our result about composition of almost-universal functions.
   Suppose that $G$ is $\epsilon$-almost XOR universal, and $G'$ is
@@ -792,7 +834,7 @@
 
 \begin{slide}
   \topic{a better MAC}
-  \head{Almost XOR-universality, 3: a better MAC}
+  \head{Almost XOR-universality, \seq: a better MAC}
 
   The security result for the UH-based MAC contains a factor $q_T$, which
   it'd be nice to remove.  Our new scheme uses an AXU hash $H\colon \keys H
@@ -817,7 +859,7 @@
 \end{slide}
 
 \begin{slide}
-  \head{Almost XOR-universality, 4: security of AXU-based MACs}
+  \head{Almost XOR-universality, \seq: security of AXU-based MACs}
   
   For the stateful scheme presented earlier, provided $q_T \le 2^l$, we have
   \begin{eqnarray*}[Ll]
@@ -827,7 +869,7 @@
 \end{slide}
 
 \begin{slide}
-  \head{Almost XOR-universality, 5: randomized AXU-based MAC}
+  \head{Almost XOR-universality, \seq: randomized AXU-based MAC}
   
   We can avoid statefulness by using randomization.  This new scheme is
   $\Xid{\mathcal{M}}{XUH$\$$}^{H, F} = (\Xid{T}{XUH$\$$}^{H, F},
diff --git a/auth-sig.tex b/auth-sig.tex
index b3322ac..8faff1e 100644
--- a/auth-sig.tex
+++ b/auth-sig.tex
@@ -29,7 +29,7 @@
   
   We recognize several different types of forgeries which can be made:
   \begin{itemize}
-  \item An \emph{existiential forgery} occurs when an adversary creates a
+  \item An \emph{existential forgery} occurs when an adversary creates a
     valid signature for some arbitrary message not of its choosing.
   \item An \emph{selective forgery} occurs when an adversary creates a valid
     signature for a message that it chooses.
@@ -183,9 +183,9 @@
 \end{slide}
 
 \begin{slide}
-  \head{Fixing RSA, 2: \PKCS1 padding (cont.)}
+  \head{\PKCS1 signature padding (cont.)}
 
-  Diagramatically, \PKCS1 signature looks like this:
+  Diagrammatically, \PKCS1 signature looks like this:
   \begin{tabular}[C]{r|c|c|c|c|c|} \hlx{c{2-6}v}
     \hex{00} & \hex{01} &
     \hex{FF} \hex{FF} \ldots \hex{FF} &
@@ -314,7 +314,7 @@
   \[ \Pr[F] = \Pr[F \land N] + \Pr[F \land \lnot N]
      \quad \text{so} \quad
      \Pr[F \land \lnot N] = \Pr[F] - \Pr[F \land N]. \]%
-  From the above discussion, we ahave
+  From the above discussion, we have
   \[ \Pr[V \land N] = \Pr[F \land N]
      \quad \text{and} \quad
      \Pr[V \land \lnot N] \ge \frac{1}{q_H} \Pr[F \land \lnot N]. \]%
@@ -563,7 +563,7 @@
   
   Most of the \ABORT statements in the main inverter routine detect incorrect
   signatures.  The final one, asserting $x \notin \Xid{I}{map}$, can't happen
-  unless the signaure is a duplicate of one we already gave.
+  unless the signature is a duplicate of one we already gave.
   
   The \ABORT{}s in $H$ and \id{sign} detect conditions in which the
   adversary has successfully distinguished its simulated environment from
diff --git a/basics.tex b/basics.tex
index 6d5be48..9c7401f 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}
 
@@ -599,7 +639,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 +656,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 +675,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 +697,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 +729,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 +742,129 @@ 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, 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 +881,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 +890,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 +921,7 @@ 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: 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 +937,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 +952,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 +971,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 +1006,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 +1020,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 +1103,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 +1129,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 +1144,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 +1175,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
diff --git a/enc-ies.tex b/enc-ies.tex
index cd0f5c6..7150019 100644
--- a/enc-ies.tex
+++ b/enc-ies.tex
@@ -1,9 +1,10 @@
 \xcalways\section{Integrated public-key encryption schemes}\x
 
 The formulation here is original work by the author.  I've tried to
-generalize the work by (among others), Shoup, and Abdalla, Bellare and
-Rogaway.  The final proof is from a Usenet article prompted by David
-Hopwood, but based on the DHAES proof by ABR.
+generalize the work by (among others), Shoup \cite{Shoup:2001:PIS}, and
+Abdalla, Bellare and Rogaway \cite{Abdalla:2001:DHIES}.  The final proof is
+from a Usenet article prompted by David Hopwood, but based on the DHIES proof
+in \cite{Abdalla:2001:DHIES}.
 
 \xcalways\subsection{Introduction and definitions}\x
 
@@ -133,8 +134,8 @@ Hopwood, but based on the DHAES proof by ABR.
   \[ \Pr[S] =
        \frac{\Adv{ohd}{\Xid{\mathcal{K}}{OWF}^{\mathcal{T}, H}}(A)}{2} +
        \frac{1}{2}. \]%
-  Let $F$ be the event that $A$ queries $H$ at $x^*$.  Then by Shoup's Lemma
-  (lemma~\ref{lem:shoup}, page~\pageref{lem:shoup}),
+  Let $F$ be the event that $A$ queries $H$ at $x^*$.  Then by 
+  Lemma~\ref{lem:shoup} (slide~\pageref{lem:shoup}),
   \[ \left|\Pr[S] - \frac{1}{2}\right| \le \Pr[F]. \]
 
   Now consider this adversary $I$, attempting to invert the one-way function.
diff --git a/enc-intro.tex b/enc-intro.tex
index 6199d4f..47a9ced 100644
--- a/enc-intro.tex
+++ b/enc-intro.tex
@@ -2,12 +2,6 @@
 
 \xcalways\subsection{Security notions and attacks}\x
 
-%%%         * Security notions and attacks: semantic security and find-then-
-%%%           guess indistinguishability; left-or-right and real-or-random
-%%%           indistinguishability; chosen plaintext and chosen ciphertext
-%%%           (lunchtime and adaptive) attacks; non-malleability; plaintext
-%%%           awareness; funny abbreviations (e.g., IND-CPA, NM-CCA2).
-
 \begin{slide}
   \head{Security notions for encryption}
 
@@ -16,7 +10,8 @@
 
 \begin{slide}
   \topic{adversarial goals}
-  \head{Encryption: adversarial goals 1}
+  \resetseq
+  \head{Encryption: adversarial goals \seq}
 
   \begin{description}
   \item [Indistinguishability (find-then-guess)] The adversary chooses two
@@ -30,7 +25,7 @@
 \end{slide}
 
 \begin{slide}
-  \head{Encryption: adversarial goals 2}
+  \head{Encryption: adversarial goals \seq}
 
   \begin{description}
   \item [Indistinguishability (left-or-right)] The adversary is given an
@@ -48,7 +43,7 @@
 \end{slide}
 
 \begin{slide}
-  \head{Encryption: adversarial goals 3}
+  \head{Encryption: adversarial goals \seq}
 
   \begin{description}
   \item [Non-malleability] An adversary cannot transform a ciphertext such
diff --git a/enc-pub.tex b/enc-pub.tex
index 985690c..2da1c82 100644
--- a/enc-pub.tex
+++ b/enc-pub.tex
@@ -947,7 +947,7 @@
 \begin{slide}
   \head{\PKCS1 encryption padding for RSA (cont.)}
 
-  Diagramatically, \PKCS1 encryption padding looks like this:
+  Diagrammatically, \PKCS1 encryption padding looks like this:
   \begin{tabular}[C]{r|c|c|c|c|} \hlx{c{2-5}v}
     \hex{00} & \hex{01} &
     \ldots\ random nonzero bytes \ldots &
@@ -1029,7 +1029,7 @@
 \end{slide}
 
 \begin{slide}
-  \head{Security of OAEP, 1: chosen plaintext attacks}
+  \head{Security of OAEP, \seq: chosen plaintext attacks}
   
   We write the encryption scheme formed by using the trapdoor one-way
   function $\mathcal{T}$ with OAEP embedding as
@@ -1151,7 +1151,7 @@ for OAEP+ which is presented in full later.
   definition is used to feed the challenge ciphertext to the plaintext
   extractor.
 
-  Quantatively, if $\mathcal{E}$ is $\epsilon$-plaintext aware, and the
+  Quantitatively, if $\mathcal{E}$ is $\epsilon$-plaintext aware, and the
   plaintext extractor runs in time $t_X(q_H)$, then
   \[ \InSec{ind-cca2}(\mathcal{E}; t, q_D, q_H) \le
      \InSec{ind-cpa}(\mathcal{E}; t + q_D t_X(q_H), q_H) + q_D \epsilon. \]%
@@ -1215,7 +1215,7 @@ for OAEP+ which is presented in full later.
       \RETURN $x$;
   \end{program}
   Firstly, we show that it still meets IND-CCA2.  Let $A'$ be an adversary
-  attacking $\mathcal{E}'$ in the IND-CCA2 sense.  Then $A$, below, acheives
+  attacking $\mathcal{E}'$ in the IND-CCA2 sense.  Then $A$, below, achieves
   the same advantage against $\mathcal{E}$.
   \begin{program}
     Adversary $A^{D(\cdot), H(\cdot)}(\cookie{find}, P)$: \+ \\
@@ -1275,9 +1275,10 @@ for OAEP+ which is presented in full later.
 
 \begin{slide}
   \topic{OAEP+}
-  \head{Plaintext-aware encryption: OAEP+ \cite{Shoup:2001:OAEPR}, 1}
+  \resetseq
+  \head{Plaintext-aware encryption: OAEP+ \cite{Shoup:2001:OAEPR}, \seq}
   
-  OAEP+ is a simple embedding scheme, very similar to OAEP, which acheives
+  OAEP+ is a simple embedding scheme, very similar to OAEP, which achieves
   plaintext-awareness.
   
   We assume that our one-way function $f_P$ operates on $n$-bit strings.  Fix
@@ -1307,7 +1308,7 @@ for OAEP+ which is presented in full later.
 \end{slide}
 
 \begin{slide}
-  \head{Plaintext-aware encryption: OAEP+, 2}
+  \head{Plaintext-aware encryption: OAEP+, \seq}
 
   %%        x <- {0, 1}^{n-2k}                r <-R {0, 1}^k
   %%                |                              |
@@ -1350,7 +1351,7 @@ for OAEP+ which is presented in full later.
 \end{slide}
 
 \begin{slide}
-  \head{Plaintext-aware encryption: OAEP+, 3}
+  \head{Plaintext-aware encryption: OAEP+, \seq}
   
   Let $\mathcal{T}$ be a trapdoor one-way function.  Then the insecurity of
   the public-key encryption scheme $\Xid{\mathcal{E}}{OAEP+}^{\mathcal{T}}$
@@ -1375,27 +1376,6 @@ for OAEP+ which is presented in full later.
   \end{eqnarray*}
 \end{slide}
 
-Before we move on to the OAEP+ security results, we state and prove the
-following lemma, due (I believe) to Victor Shoup.
-
-\begin{lemma}[Shoup]
-  \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}
-
 \begin{proof}[Proof of the main OAEP+ result]
   
   We assume throughout that, before querying its $H'$ oracle at $x \cat r$,
@@ -1412,12 +1392,12 @@ following lemma, due (I believe) to Victor Shoup.
   
   \paragraph{Game $\G0$}
   This is effectively the original attack game: the adversary chooses two
-  plaintexts: one is chosen unformly at random, the adversary is given the
+  plaintexts: one is chosen uniformly at random, the adversary is given the
   ciphertext and asked to identify which plaintext was chosen.  Label the
   selected plaintext $x^*$, and the target ciphertext $y^*$.  Let $c^*$,
   $s^*$, $t^*$ and $w^*$ be the intermediate results of the OAEP+ padding, as
   described above.  Let $S_0$ be the event that the adversary wins the game.
-  Our objective is to bound the probabilty $\Pr[S_0] =
+  Our objective is to bound the probability $\Pr[S_0] =
   (\Adv{ind-cpa}{\Xid{\mathcal{E}}{OAEP+}^{\mathcal{T}}}(A) + 1)/2$.
 
   \paragraph{Game $\G1$}
@@ -1499,7 +1479,7 @@ following lemma, due (I believe) to Victor Shoup.
   Now observe that, if $F_1$ doesn't occur, Games $\G0$ and~$\G1$ are
   indistinguishable.  So
   \[ \Pr[S_0 \land \lnot F_1] = \Pr[S_1 \land \lnot F_1], \]
-  so by Shoup's lemma,
+  so by Lemma~\ref{lem:shoup} (slide~\pageref{lem:shoup}),
   \[ |{\Pr[S_0]} - \Pr[S_1]| \le \Pr[F_1]. \]
   Rearranging yields:
   \[ \Adv{ind-cpa}{\Xid{\mathcal{E}}{OAEP+}^{\mathcal{T}}}(A)
diff --git a/enc-symm.tex b/enc-symm.tex
index e0f3f01..18a05c6 100644
--- a/enc-symm.tex
+++ b/enc-symm.tex
@@ -35,7 +35,7 @@
   against chosen-plaintext and chosen-ciphertext attacks.  To make life more
   complicated, we have three different indistinguishability notions.
 
-  We use the same notation to decscribe the decryption oracles provided in
+  We use the same notation to describe the decryption oracles provided in
   various types of attacks:
   \begin{tabular}[C]{l Mc Mc }
                                 \hlx*{hv}
@@ -318,7 +318,7 @@
      
      Now we show that we can't obtain a better reduction.  Suppose that
      $\mathcal{E} = (E, D)$ is $(t, q_E, q_D, \epsilon)$-secure in the FTG
-     sense.  We contruct a \emph{$p$-leaky} version, $\mathcal{E}' = (E',
+     sense.  We construct a \emph{$p$-leaky} version, $\mathcal{E}' = (E',
      D')$.  Let $\id{maybe}(p)$ denote a function which returns $1$ with
      probability $p$.
      \begin{program}
@@ -506,7 +506,8 @@
 
 \begin{slide}
   \topic{ECB}
-  \head{Electronic Code Book (ECB), 1: description}
+  \resetseq
+  \head{Electronic Code Book (ECB), \seq: description}
   
   We define the scheme $\Xid{\mathcal{E}}{ECB}^E = (\Xid{E}{ECB}^E,
   \Xid{D}{ECB}^E))$ by setting $\keys\Xid{\mathcal{E}}{ECB}^E = \{0, 1\}^k$
@@ -527,7 +528,7 @@
 \end{slide}
 
 \begin{slide}
-  \head{Electronic Code Book (ECB), 2: analysis}
+  \head{Electronic Code Book (ECB), \seq: analysis}
   
   ECB fails to disguise equality of message blocks.  Hence, it is insecure in
   the left-or-right sense.
@@ -549,7 +550,8 @@
 
 \begin{slide}
   \topic{stateful counter mode}
-  \head{Counter (CTR), 1: a stateful mode}
+  \resetseq
+  \head{Counter (CTR), \seq: a stateful mode}
   
   We define two schemes.  Firstly, a stateful-sender scheme
   $\Xid{\mathcal{E}}{CTRS}^E = (\Xid{E}{CTRS}^E, \Xid{D}{CTRS}^E))$.  We set
@@ -574,7 +576,7 @@
 \end{slide}
 
 \begin{slide}
-  \head{Counter (CTR), 2: analysis of the stateful version}
+  \head{Counter (CTR), \seq: analysis of the stateful version}
   
   We write $q' = q\mu/l$ for the total number of blocks queried by the
   adversary, and we restrict our attention to the case $n \le 2^l$.
@@ -611,7 +613,7 @@
 
 \begin{slide}
   \topic{randomized counter mode}
-  \head{Counter (CTR), 3: a randomized mode}
+  \head{Counter (CTR), \seq: a randomized mode}
   
   The randomized scheme $\Xid{\mathcal{E}}{CTR$\$$}^E = (\Xid{E}{CTR$\$$}^E,
   \Xid{D}{CTR$\$$}^E))$ differs from the stateful scheme in the encryption
@@ -637,7 +639,7 @@
 \end{slide}
 
 \begin{slide}
-  \head{Counter (CTR), 4: analysis of the randomized version}
+  \head{Counter (CTR), \seq: analysis of the randomized version}
 
   The randomized mode remains secure so long as a counter is never repeated.
   This occurs with probability no greater than
@@ -664,7 +666,8 @@
 
 \begin{slide}
   \topic{CBC}
-  \head{Ciphertext Block Chaining (CBC), 1: description}
+  \resetseq
+  \head{Ciphertext Block Chaining (CBC), \seq: description}
 
   We define the scheme $\Xid{\mathcal{E}}{CBC}^E = (\Xid{E}{CBC}^E,
   \Xid{D}{CBC}^E))$ by setting $\keys\Xid{\mathcal{E}}{CBC}^E = \{0, 1\}^k$
@@ -689,7 +692,7 @@
 \end{slide}
 
 \begin{slide}
-  \head{Ciphertext Block Chaining (CBC), 2: analysis}
+  \head{Ciphertext Block Chaining (CBC), \seq: analysis}
 
   As before, we set $q' = q\mu/l$ as the number of blocks queried by an
   adversary attacking the encryption scheme.
@@ -704,7 +707,7 @@
 
 \begin{slide}
   \topic{requirement for random IVs in CBC mode}
-  \head{Ciphertext Block Chaining (CBC), 3: on randomness of IVs}
+  \head{Ciphertext Block Chaining (CBC), \seq: on randomness of IVs}
   
   The initialization vector used in CBC encryption must be \emph{a priori}
   unpredictable to the adversary.  Suppose that $P(i)$, given an IV for a
@@ -832,7 +835,7 @@
   \topic{strong MACs provide INT-CTXT}
   \head{A strong MAC provides integrity of ciphertexts}
 
-  That's a very nice result, but how do we acheive INT-CTXT?  Well, the
+  That's a very nice result, but how do we achieve INT-CTXT?  Well, the
   game in the definition looks very much like the forgery games we played
   when we were thinking about MACs.
   
@@ -928,7 +931,7 @@
   We begin with a few words on our approach, before we embark on the proof
   proper.
   
-  To demonstrate the generic insecurity of a scheme, we assume the existance
+  To demonstrate the generic insecurity of a scheme, we assume the existence
   of an encryption scheme and MAC (since if they don't exist, the result is
   vacuously true) and construct modified schemes whose individual security
   relates tightly to the originals, but the combined scheme is weak.
@@ -1144,7 +1147,7 @@
         \ELSE \RETURN $V(x, \tau)$;
     \end{program}
     Here, $A$ simply simulates the environment expected by $A'$.  It is clear
-    that $A$ succeeds whenver $A'$ returns a valid tag for a \emph{new}
+    that $A$ succeeds whenever $A'$ returns a valid tag for a \emph{new}
     message.  However, suppose that $A'$ returns a new tag $\tau'$ for some
     old message $x$, for which the tag $\tau$ was returned by the tagging
     oracle.  Let $x_0$, $\tau_0$ and $\tau'_0$ be the first bits of $x$,
diff --git a/ips.cls b/ips.cls
index 2ecc62a..f5f20d7 100644
--- a/ips.cls
+++ b/ips.cls
@@ -142,6 +142,11 @@
   \def\topic{\sm@auxwrite{topic}}
 \fi
 
+\newcounter{sequence}
+\def\thesequence{\arabic{sequence}}
+\def\seq{\stepcounter{sequence}\thesequence}
+\def\resetseq{\setcounter{sequence}{0}}
+
 \def\head#1{{\sffamily\bfseries\large #1}\par}
 
 %%%------ Page layout for notes ---------------------------------------------
-- 
2.11.0

