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) \\
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) \\
\begin{eqnarray*}[Ll]
\InSec{suf-cma}(\Xid{\mathcal{M}}{XUH$\$$}^{H, F}; t, q_T, q_V) \\
& \le (q_V + 1)
\begin{eqnarray*}[Ll]
\InSec{suf-cma}(\Xid{\mathcal{M}}{XUH$\$$}^{H, F}; t, q_T, q_V) \\
& \le (q_V + 1)
$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$ 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
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
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
\[ 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$.
\[ 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)$.