to a valid message-tag pair $(m,t)$, the probability of a successful substitution is bounded by $$\label{eq:thm-WCA}
    \Pr\big\{f_K(m_{\text E})=t_{\text E}\,\big|\, f_K(m)=t\big\} 
    \le {\varepsilon}+|{\mathcal{T}}|{\varepsilon}'.$$

The first inequality is obtained by applying Lemma \[lemma:subset\] to the set $\{k\in{\mathcal{K}}:f_k(m_{\text E})=t_{\text E}\}$. Since the hash function family is ${\varepsilon}$-ASU$_2$ (Def. 3(a)), this set has the size $|{\mathcal{K}}|/|{\mathcal{T}}|$, and $$\label{WCA-1}
    \Pr\big\{f_K(m_{\text E})=t_{\text E}\big\}
    \le\frac{|{\mathcal{K}}|}{|{\mathcal{T}}|}\frac1{|{\mathcal{K}}|}+{\varepsilon}'
    =\frac1{|{\mathcal{T}}|}+{\varepsilon}'.$$ To bound the probability that the adversary sees $(m,t)$ *and* performs a successful substitution attack, we denote the subset of authentication key values that gives $(m,t)$ by $$\label{eq:WCA-2}
  {\mathcal{K}}' = \{k\in{\mathcal{K}}: f_k(m)=t\},$$ and where the attack succeeds by $${\mathcal{K}}''=\{k\in{\mathcal{K}}: f_k(m_{\text E}) = t_{\text E}\wedge f_k(m) = t \}.
    \label{eq:WCA-3}$$ We know from Def. 3 that $|{\mathcal{K}}'|=|{\mathcal{K}}|/|{\mathcal{T}}|$ and that $|{\mathcal{K}}''|={\varepsilon}|{\mathcal{K}}|/|{\mathcal{T}}|$. So using Theorem \[lemma:sub-subset\], we have $$\label{eq:WCA-4}
    \begin{split}
      \Pr\big\{f_K(m_{\text E})&=t_{\text E}\,\big|\, f_K(m)=t\big\} =P_K({\mathcal{K}}''\,|\,{\mathcal{K}}')
      \le \frac{|{\mathcal{K}}''|}{|{\mathcal{K}}'|} + \frac{|{\mathcal{K}}|}{|{\mathcal{K}}'|}{\varepsilon}' \le {\varepsilon}+|{\mathcal{T}}|{\varepsilon}'.
    \end{split}$$ $\square$

This theorem tells us that the previous example really is a worst-case scenario, so that the upper bound for Eve’s success probability after seeing a message-tag pair is ${\varepsilon}+|{\mathcal{T}}|{\varepsilon}'$. Conversely, the example shows that the bound is sharp: there are situations where the bound is reached, so the bound cannot be lowered if one wants information-theoretic security.

In the Universal Composability 