Fix typos. Replace proof that PRPs are PRFs. Other fixes.

[doc/ips] / auth-mac.tex

diff --git a/auth-mac.tex b/auth-mac.tex
index 0c3e6e5..8b4eb8a 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,7 +102,8 @@
 
 \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


@@ -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


@@ -156,12 +158,44 @@
      \InSec{prf}(F; t + O(q), q) + (q_V + 1)2^{-L}. \]%
 \end{slide}
 
      \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,7 +377,7 @@
 \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,
 
   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}
 \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


@@ -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.


@@ -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
 
   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
   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
   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 +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
   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 +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}}. \]%
   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 +612,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 +633,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 +652,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 +674,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 +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). \]
   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 +707,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 +777,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 +798,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 +820,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 +834,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 +859,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 +869,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},