Miscellaneous rewordings and fixings.

[doc/ips] / auth-mac.tex

diff --git a/auth-mac.tex b/auth-mac.tex
index 0c3e6e5..60e0034 100644 (file)
--- a/auth-mac.tex
+++ b/auth-mac.tex
@@ -21,7 +21,8 @@
 
 \begin{slide}
   \topic{informal security notion}
 
 \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
   
   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}
 
 \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}
 
   We perform the following experiment with the adversary.
   \begin{program}


@@ -60,7 +61,7 @@
 \end{slide}
 
 \begin{slide}
 \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
 
   The \emph{success probability} of an adversary $A$ against the MAC
   $\mathcal{M}$ in the sense of SUF-CMA is


@@ -101,11 +102,12 @@
 
 \begin{slide}
   \topic{PRFs are MACs}
 
 \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
   
   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

-  + q_V + 1$, $t = t' + O(q)$, and $\epsilon \le \epsilon' + (q_V + 1)
+  + q_V + 1$, $t = t' + O(q)$, and $\epsilon' \le \epsilon + (q_V + 1)

   2^{-L}$.  The constant hidden by the $O(\cdot)$ is small and depends on the
   model of computation.
   
   2^{-L}$.  The constant hidden by the $O(\cdot)$ is small and depends on the
   model of computation.
   


@@ -118,7 +120,7 @@
 \end{slide}
 
 \begin{slide}
 \end{slide}
 
 \begin{slide}

-  \head{PRFs are MACs, 2: the distinguisher}
+  \head{PRFs are MACs, \seq: the distinguisher}

 
   \begin{program}
     Distinguisher $D^{F(\cdot)}$: \+ \\
 
   \begin{program}
     Distinguisher $D^{F(\cdot)}$: \+ \\


@@ -137,7 +139,7 @@
 \end{slide}
 
 \begin{slide}
 \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
 
   The distinguisher simulates the tagging and verification oracles for the
   MAC forger, using its supplied oracle.  If the forger succeeds, then the


@@ -150,18 +152,50 @@
   $A$ does when it's given a random function.  But we know that the
   probability of it successfully guessing the MAC for a message for which it
   didn't query $T$ can be at most $(q_V + 1) 2^{-L}$.  So
   $A$ does when it's given a random function.  But we know that the
   probability of it successfully guessing the MAC for a message for which it
   didn't query $T$ can be at most $(q_V + 1) 2^{-L}$.  So

-  \[ \Adv{prf}{F}(D) \le \Succ{suf-cma}{F}(A) - (q_V + 1) 2^{-L}. \]
+  \[ \Adv{prf}{F}(D) \ge \Succ{suf-cma}{F}(A) - (q_V + 1) 2^{-L}. \]

   Let $q = q_T + q_V + 1$; then counting, rearranging, maximizing yields
   \[ \InSec{suf-cma}(F; t, q_T, q_V) \le
      \InSec{prf}(F; t + O(q), q) + (q_V + 1)2^{-L}. \]%
 \end{slide}
 
   Let $q = q_T + q_V + 1$; then counting, rearranging, maximizing yields
   \[ \InSec{suf-cma}(F; t, q_T, q_V) \le
      \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
 \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%
   \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.,
     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.
   \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]
   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*}
         &= \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}
 \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
   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}
   \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
   \end{itemize}
 
   It would be nice to have a construction whose security was provably related


@@ -317,7 +357,7 @@
 \end{slide}
 
 \begin{slide}
 \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
  
   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,15 +377,15 @@
 \end{slide}
 
 \begin{slide}
 \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,
   for any adversary $A$ constrained to run in time $t$ and permitted $q$
   oracle queries,
   \[ \Pr[K \getsr \{0, 1\}^k;
 
   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,
   for any adversary $A$ constrained to run in time $t$ and permitted $q$
   oracle queries,
   \[ \Pr[K \getsr \{0, 1\}^k;

-         (x, y) \gets A^{F_K(\cdot)}] \le \epsilon :
-         x \ne y \land F_K(x) = F_K(y) \]%
+         (x, y) \gets A^{F_K(\cdot)} :
+         x \ne y \land F_K(x) = F_K(y)] \le \epsilon \]%

   
   If $H_K$ is a $(t, q_T, q_V, \epsilon)$-secure MAC on $k$-bit messages, and
   moreover $(t, q_T + q_V, \epsilon')$-weakly collision resistant, then
   
   If $H_K$ is a $(t, q_T, q_V, \epsilon)$-secure MAC on $k$-bit messages, and
   moreover $(t, q_T + q_V, \epsilon')$-weakly collision resistant, then


@@ -353,12 +393,12 @@
 \end{slide}
 
 \begin{slide}
 \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
 
   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

-  $\epsilon$.  We construct an adversary $A'$ which forces a $H$ tag for a
-  $k$-bit in essentially the same time.
+  $\epsilon$.  We construct an adversary $A'$ which forges an $H$-tag for a
+  $k$-bit message in essentially the same time.

   \begin{program}
     Adversary $A'^{T(\cdot), V(\cdot, \cdot)}$ \+ \\
       $K \getsr \{0, 1\}^k$; \\
   \begin{program}
     Adversary $A'^{T(\cdot), V(\cdot, \cdot)}$ \+ \\
       $K \getsr \{0, 1\}^k$; \\


@@ -373,7 +413,7 @@
 \end{slide}
 
 \begin{slide}
 \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
 
   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}
 \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 =
 
   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*}
   $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
     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.
   \end{eqlines*}
   Decide whether each of these constructions is secure.  A full proof is
   rather hard: an informal justification would be good.


@@ -445,38 +485,39 @@
   function $F$.  For the sake of simplicity, we allow the adversary $A$
   to query on \emph{padded} messages, rather than the raw unpadded
   messages.  We count the number $q'$ of individual message blocks.
   function $F$.  For the sake of simplicity, we allow the adversary $A$
   to query on \emph{padded} messages, rather than the raw unpadded
   messages.  We count the number $q'$ of individual message blocks.

-
-  As the game with $A$ progresses, we can construct a directed
-  \emph{graph} of the query results so far.  We start with a node
-  labelled $I$.  When processing an $H$-query, each time we compute $t'
-  = F(t \cat x_i)$, we add a node $t'$, and an edge $x_i$ from $t$ to
-  $t'$.  The `bad' event occurs whenever we add an edge to a previously
-  existing node.  We must show, firstly, that the
-  adversary cannot distinguish $H$ from a random function unless the bad
-  event occurs; and, secondly, that the bad event doesn't occur very
-  often.
+  
+  As the game with $A$ progresses, we can construct a directed \emph{graph}
+  of the query results so far.  We start with a node labelled $I$.  When
+  processing an $H$-query, each time we compute $t' = F(t \cat x_i)$, we add
+  a node $t'$, and an edge $x_i$ from $t$ to $t'$.  The `bad' event occurs
+  whenever we add an edge to a previously existing node.  We must show,
+  firstly, that the adversary cannot distinguish $H$ from a random function
+  unless the bad event occurs; and, secondly, that the bad event doesn't
+  occur very often.

 
   The latter is easier: our standard collision bound shows that the bad
 
   The latter is easier: our standard collision bound shows that the bad

-  event occurs during the game with probability at most $q'(q' - 1)/2$.
-
+  event occurs during the game with probability at most $q'(q' - 1)/2^{t+1}$.
+  

   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
   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
-  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
-  graph; then either the bad event occurs or we create a new node for
-  the result, and because $F$ is a random function, the answer is
-  uniformly random.  Finally, we consider the case where the query is a
-  prefix of some earlier query, or queries.  But these were computed at
-  random at the time.
+  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 a \emph{prefix} of some
+  earlier query, then the answer is the value of some internal node which
+  hasn't been revealed before; however, the value of that internal node was
+  chosen uniformly at random (we claim).  Finally, if the query is not a
+  prefix of any previous query, then we add a new edge to our graph.  If the
+  bad event doesn't occur, we must add a new node for the result, and the
+  value at that node will be uniformly random, because $F$ is a random
+  function being evaluated at a new point -- this is the only time we add new
+  nodes to the graph, justifying the claim made earlier.

 
   At the end of all of this, we see that
   \[ \InSec{prf}(T^0; t, q) \le
 
   At the end of all of this, we see that
   \[ \InSec{prf}(T^0; t, q) \le

-       \InSec{prf}(F; t, q') + \frac{q'(q' - 1)}{2} \]%
+       \InSec{prf}(F; t, q') + \frac{q'(q' - 1)}{2^{t+1}} \]%

   and hence
   \[ \InSec{suf-cma}(\mathcal{M}^0; t, q) \le 
   and hence
   \[ \InSec{suf-cma}(\mathcal{M}^0; t, q) \le 

-       \InSec{prf}(F; t, q') + \frac{q'(q' - 1)}{2} + \frac{1}{2^t}. \]%
+       \InSec{prf}(F; t, q') + \frac{2 q'(q' - 1) + 1}{2^{t+1}}. \]%

 
   Now we turn our attention to $T^1$.  It's clear that we can't simulate
   $T^1$ very easily using an oracle for $F$, since we don't know $K$
 
   Now we turn our attention to $T^1$.  It's clear that we can't simulate
   $T^1$ very easily using an oracle for $F$, since we don't know $K$


@@ -511,7 +552,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
   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
   \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 +567,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
   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}$.
   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 +575,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}}. \]%
   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}
 \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
   
   Consider a family of hash functions $H\colon \keys H \times \dom H \to
   \ran H$.  We define


@@ -571,7 +613,7 @@
 
 \begin{slide}
   \topic{dynamic view}
 
 \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}
   
   Suppose that $H$ is $\epsilon$-almost universal.  Consider this experiment:
   \begin{program}


@@ -592,7 +634,7 @@
 \end{slide}
 
 \begin{slide}
 \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
   
   Now we treat $\rho$ as a random variable, selected from some distribution
   $P$ on the set $\{0, 1\}^*$.  We see that


@@ -611,7 +653,7 @@
 
 \begin{slide}
   \topic{composition}
 
 \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
   
   Suppose that $G$ is $\epsilon$-almost universal, and $G'$ is
   $\epsilon'$-almost universal, and $\dom G = \ran G'$.  We define the


@@ -633,14 +675,14 @@
 
 \begin{slide}
   \topic{the collision game}
 
 \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$.
   
   
   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}
   with $|Y| \le q$.  Then
   \[ \InSec{uh-set}(H; q) \le \frac{q(q - 1)}{2} \cdot \InSec{uh}(H) .\]
 \end{slide}


@@ -657,7 +699,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). \]
   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
   \[ \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 +708,10 @@
 
 \begin{slide}
   \topic{a MAC}
 
 \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]
   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 +778,8 @@
 
 \begin{slide}
   \topic{almost XOR-universality}
 
 \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
   
   Consider a family of hash functions $H\colon \keys H \times \dom H \to
   \{0, 1\}^L$.  Define


@@ -756,7 +799,7 @@
   technique as for almost universal functions.
   
   If $H$ is $2^{-L}$-almost XOR universal then we say that $H$ is
   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}
 \end{slide}
 
 \begin{proof}


@@ -778,7 +821,7 @@
 
 \begin{slide}
   \topic{composition}
 
 \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
   
   We extend our result about composition of almost-universal functions.
   Suppose that $G$ is $\epsilon$-almost XOR universal, and $G'$ is


@@ -792,7 +835,7 @@
 
 \begin{slide}
   \topic{a better MAC}
 
 \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
 
   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 +860,7 @@
 \end{slide}
 
 \begin{slide}
 \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]
   
   For the stateful scheme presented earlier, provided $q_T \le 2^l$, we have
   \begin{eqnarray*}[Ll]


@@ -827,7 +870,7 @@
 \end{slide}
 
 \begin{slide}
 \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},
   
   We can avoid statefulness by using randomization.  This new scheme is
   $\Xid{\mathcal{M}}{XUH$\$$}^{H, F} = (\Xid{T}{XUH$\$$}^{H, F},