bounded by $$\label{eq:WCA-cor}
     \tfrac12\sum_{k:f_k(m)=t}\bigg|P_K(k\,|\,f_K(m)=t)
     -\frac1{|\{k:f_k(m)=t\}|}\bigg| 
     \le  |{\mathcal{T}}|{\varepsilon}'.$$

We use ${\mathcal{K}}' = \{k\in{\mathcal{K}}: f_k(m)=t\}$ and immediately obtain the bound from Theorem \[lemma:cor\]: $$\label{eq:WCA-cor-1}
     \tfrac1{2}\sum_{k\in{\mathcal{K}}'}\Big|P_K(k\,|\,{\mathcal{K}}')
     -\frac1{|{\mathcal{K}}'|}\Big| 
     \le \frac{|{\mathcal{K}}|}{|{\mathcal{K}}'|}{\varepsilon}'
     =|{\mathcal{K}}|\frac{|{\mathcal{T}}|}{|{\mathcal{K}}|}{\varepsilon}'=|{\mathcal{T}}|{\varepsilon}'.$$ $\square$

Again, the bound is sharp because of the example: there are situations where the bound is reached, so the bound cannot be lowered if one wants information-theoretic security. Note that, again, that this depends on $(m,t)$, and a similar argument as that used above applies to Eve’s success rate. The upper bound is only reached in beneficial situations (for Eve).

The example shows that the bounds cannot be lowered, but are only reached for certain $(m,t)$. This means that the notion of ITS used here is ill suited for the situation. It works well for perfect keys, because there, the probability of a successful attack is equally bounded, with a low bound. It is clear that the situation is the same whether one looks at guessing probability or trace distance; there is a substantial, but non-constant increase. This is the reason to turn to the notion of indistinguishability, which is better suited for this situation.

Indistinguishability from Ideal Authentication {#sec:UC-security}
==============================================

The notion of witness indistinguishability was first introduced in [@FS]. Here, 