nonzero. This means that the authentication key is a random variable $K$ to Eve, and we use ${\varepsilon}'$ to denote its trace distance to the uniform.

We will start by giving an example of how large Eve’s probability for a successful substitution attack can become, even when using a SU$_2$ family. Since we are talking about a substitution attack, we need to calculate the probability conditioned on Eve having seen a message-tag pair $(m,t)$ from Alice. One possible distribution is $$\label{eq:key-distr}
  P_K(k)=
  \begin{cases}
    \frac1{|{\mathcal{K}}|}+{\varepsilon}',&\text{if }k\in{\mathcal{K}}_+=\{k_+\}\\
    \frac1{|{\mathcal{K}}|}-{\varepsilon}'\frac1{|{\mathcal{K}}_-|},
    &\text{if } k\in{\mathcal{K}}_-\\
    \frac1{|{\mathcal{K}}|},&\text{otherwise}.
  \end{cases}$$ This has trace distance ${\varepsilon}'$ to the uniform. If ${\varepsilon}'>1/|{\mathcal{K}}|$, the set ${\mathcal{K}}_-$ must contain more than one value. (Compare with the distribution used in [@CL] where $P_K(k)=0$ if $k\in{\mathcal{K}}_-$; $P_K(k)=1/(|{\mathcal{K}}|-|{\mathcal{K}}_-|)$ if $k\in{\mathcal{K}}_+={\mathcal{K}}\setminus{\mathcal{K}}_-$; and ${\varepsilon}'=|{\mathcal{K}}_-|/|{\mathcal{K}}|$.) It is easy to see that Eve’s probability for success, without more information on $K$, is maximal if she chooses $t_{\text E}=f_{k_+}(m_{\text E})$ and $m_{\text E}$ is such that $t_{\text E}\neq{}f_{k_-}(m_{\text E})$ for all $k_-\in{\mathcal{K}}_-$. Since the hash function family is SU$_2$, $|\{k:f_k(m_{\text E})=t_{\text E}\}|=|{\mathcal{K}}|/|{\mathcal{T}}|$, and this set contains $k_+$ but excludes ${\mathcal{K}}_-$ so that $$\begin{split}
    \Pr\big\{f_{K}(m_{\text E})=t_{\text E}\big\}
    =\frac1{|{\mathcal{K}}|}+{\varepsilon}'+\Big(\frac{|{\mathcal{K}}|}{|{\mathcal{T}}|}-1\Big)\frac1{|{\mathcal{K}}|}
    =\frac{|{\mathcal{K}}|}{|{\mathcal{T}}|}\frac1{|{\mathcal{K}}|}+{\varepsilon}'
    =\frac1{|{\mathcal{T}}|}+{\varepsilon}'.
  \end{split}\label{eq:2}$$ It is also easy to see that Eve’s probability for success 