Remove unnecessary $2^{-L}$ term from the AXU-hashing result.

[doc/ips] / auth-mac.tex

diff --git a/auth-mac.tex b/auth-mac.tex
index 67489f0..e9c9684 100644 (file)
--- a/auth-mac.tex
+++ b/auth-mac.tex
@@ -864,7 +864,7 @@
   For the stateful scheme presented earlier, provided $q_T \le 2^l$, we have
   \begin{eqnarray*}[Ll]
      \InSec{suf-cma}(\Xid{\mathcal{M}}{XUH}^{H, F}; t, q_T, q_V) \\
-     & \le (q_V + 1)(\InSec{prf}(F; t, q_T + 1) + \InSec{xuh}(H) + 2^{-L}).
+     & \le (q_V + 1)(\InSec{prf}(F; t, q_T + 1) + \InSec{xuh}(H)).
   \end{eqnarray*}
 \end{slide}
 
@@ -888,7 +888,7 @@
   \begin{eqnarray*}[Ll]
      \InSec{suf-cma}(\Xid{\mathcal{M}}{XUH$\$$}^{H, F}; t, q_T, q_V) \\
      & \le (q_V + 1)
-         \Bigl(\InSec{prf}(F; t, q_T + 1) + \InSec{xuh}(H) + 2^{-L} +
+         \Bigl(\InSec{prf}(F; t, q_T + 1) + \InSec{xuh}(H) +
                \frac{q_T(q_T - 1)}{2^{l+1}}\Bigr).
   \end{eqnarray*}
 \end{slide}
@@ -945,7 +945,8 @@
   $F$ is random, and let $N$ be the event that the nonce $s$ returned by $A$
   is not equal to any nonce $s_i$ returned by the tagging oracle.  Suppose
   $N$ occurs: then the random function $F$ has never been queried before at
-  $F$, and $\Pr[F(s) = \sigma \xor H_K(m)]$ is precisely $2^{-L}$.
+  $F$, and $\Pr[S \mid N] = \Pr[F(s) = \sigma \xor H_K(m)]$ is precisely
+  $2^{-L}$.
   
   So suppose instead that $N$ doesn't occur.  Then, since the $s_i$ are
   distinct, there is a unique $i$ such that $s = s_i$.  For $A$ to win, we
@@ -959,26 +960,22 @@
   \[ H_K(m_i) \xor H_K(m) = \sigma \xor \sigma_i. \]
   Since the $s_i$ are distinct and $F$ is a random function, the $\sigma_i$
   are independent uniformly-distributed random strings from $\{0, 1\}^L$.
-  Hence the collision-finder $C$ succeeds with probability $\Pr[S \land
-  \lnot N] \le \InSec{xuh}(H)$.
+  Hence the collision-finder $C$ succeeds with probability $\Pr[S \mid
+  \bar{N}] \le \InSec{xuh}(H)$.
 
   Wrapping up, we have
   \begin{eqnarray*}[rl]
     \Adv{prf}{F}(D)
     & \ge \Succ{suf-cma}{\Xid{\mathcal{M}}{XUH}^{H, F}}(A) -
-      (\Pr[S \mid N] \Pr[N] + \Pr[S \mid \lnot N] \Pr[\lnot N]) \\
+      (\Pr[S \mid N] \Pr[N] + \Pr[S \mid \bar{N}] \Pr[\bar{N}]) \\
     & \ge \Succ{suf-cma}{\Xid{\mathcal{M}}{XUH}^{H, F}}(A) -
-      (2^{-L} + \InSec{xuh}(H)).
+      (2^{-L} \Pr[N] + \InSec{xuh}(H) \Pr[\bar{N}]) \\
+    & \ge \Succ{suf-cma}{\Xid{\mathcal{M}}{XUH}^{H, F}}(A) -
+      \InSec{xuh}(H).
   \end{eqnarray*}
   Maximizing and rearranging yields the required result.
 \end{proof}
 
-\begin{remark*}
-  Note that our bound has a $2^{-L}$ term in it that's missing from
-  \cite{Goldwasser:1999:LNC}.  We believe that their proof is wrong in its
-  handling of the XOR-collision probability.
-\end{remark*}
-
 \endinput
 
 %%% Local Variables: