distance of the conditional distribution of $x$ on a subset ${\mathcal{X}}'\subseteq{\mathcal{X}}$. This will be useful when discussing trace distance in relation to security later.

\[lemma:cor\] If the trace distance between $P_X$ and the uniform distribution is ${\varepsilon}$, then given a subset ${\mathcal{X}}'\subseteq{\mathcal{X}}$, the conditional distribution of $x$ on ${\mathcal{X}}'$ has trace distance to the uniform (on ${\mathcal{X}}'$) that is bounded by $$\label{eq:cor}
    \tfrac12\sum_{x\in{\mathcal{X}}'}\Big|P_X(x\,|\,{\mathcal{X}}')-\frac1{|{\mathcal{X}}'|}\Big| 
    \le \frac{|{\mathcal{X}}|}{|{\mathcal{X}}'|}{\varepsilon}.$$ For certain subsets ${\mathcal{X}}'$, the bound is reached.

It is straightforward to see that $$\label{eq:cor1}
\begin{aligned}
\tfrac12\sum_{x\in{\mathcal{X}}'}&\Big|P_X(x\, |\, {\mathcal{X}}') - \frac1{|{\mathcal{X}}'|}\Big| 
= P_X({\mathcal{X}}_+\cap {\mathcal{X}}' \,|\, {\mathcal{X}}') - \frac{|{\mathcal{X}}_+\cap{\mathcal{X}}'|}{|{\mathcal{X}}'|}
\le \frac{|{\mathcal{X}}|}{|{\mathcal{X}}'|}{\varepsilon},
\end{aligned}$$ where the inequality follows from Theorem \[lemma:sub-subset\]. The bound is reached when ${\mathcal{X}}_+\cup{\mathcal{X}}_-\subseteq{\mathcal{X}}'$.$\square$

Information-theoretic security with partially known key {#sec:ITS-security}
=======================================================

In this section we analyse security of the authentication scheme under study in information-theoretic setting, in the scenario where the key has a small but non-zero trace distance to the uniform. The WCA scheme uses ${\varepsilon}$-ASU$_2$ hashing, and is ${\varepsilon}$-secure, meaning that the probability of success in a substitution attack is bounded above by ${\varepsilon}$, if the authentication key is uniformly distributed (perfect). We will now analyse what happens when this is not the case, when the trace distance to the uniform is 