logarithm. Hence, the key-consumption rate of WCA is logarithmic in the message length.

Probabilities of sets with non-uniform underlying distribution {#sec:trace-distance}
==============================================================

In what follows, we will need some simple results of probabilities of subsets of key values, or hash functions, when the key is ${\varepsilon}$-perfect. In general we denote the probability of a subset of values ${\mathcal{X}}'\subseteq{\mathcal{X}}$ by $$\begin{aligned}
  P_X({\mathcal{X}}') = \sum_{x\in{\mathcal{X}}'}P_X(x).\end{aligned}$$ First we note a simple property of the probability of a subset of ${\mathcal{X}}$, when the distribution has a nonzero trace distance to the uniform distribution.

\[lemma:subset\] If the trace distance between $P_X$ and the uniform distribution is ${\varepsilon}$, then for any subset ${\mathcal{X}}'\subseteq{\mathcal{X}}$, $$\label{eq:subset}
    \Big|P_X({\mathcal{X}}')-\frac{|{\mathcal{X}}'|}{|{\mathcal{X}}|}\Big| \le {\varepsilon}.$$ Also, there are subsets that reach the bound.

With ${\mathcal{X}}_+:=\{x\in{\mathcal{X}}:P_X(x)>1/|{\mathcal{X}}|\}$ and ${\mathcal{X}}_-:=\{x\in{\mathcal{X}}:P_X(x)<1/|{\mathcal{X}}|\}$, it is straightforward to see that $$\begin{split}
      {\varepsilon}=\tfrac12\sum_{x\in{\mathcal{X}}}\Big|P_X(x)-\frac1{|{\mathcal{X}}|}\Big|
      =P_X({\mathcal{X}}_+)-\frac{|{\mathcal{X}}_+|}{|{\mathcal{X}}|}=\frac{|{\mathcal{X}}_-|}{|{\mathcal{X}}|}-P_X({\mathcal{X}}_-).
    \end{split}$$ Now, for any subset ${\mathcal{X}}'\subseteq{\mathcal{X}}$, we have $$\begin{split}
      P_X({\mathcal{X}}')-\frac{|{\mathcal{X}}'|}{|{\mathcal{X}}|}
      \le P_X({\mathcal{X}}'\cap{\mathcal{X}}_+)-\frac{|{\mathcal{X}}'\cap{\mathcal{X}}_+|}{|{\mathcal{X}}|}
      \le P_X({\mathcal{X}}_+)-\frac{|{\mathcal{X}}_+|}{|{\mathcal{X}}|}={\varepsilon}\end{split}$$ and also $$\begin{aligned}
      \frac{|{\mathcal{X}}'|}{|{\mathcal{X}}|}-P_X({\mathcal{X}}') 
      \le \frac{|{\mathcal{X}}'\cap{\mathcal{X}}_-|}{|{\mathcal{X}}|}-P_X({\mathcal{X}}'\cap{\mathcal{X}}_-)
      \le \frac{|{\mathcal{X}}_-|}{|{\mathcal{X}}|} - P_X({\mathcal{X}}_-)={\varepsilon}. 
    \end{aligned}$$ This proves the inequality, and the subsets ${\mathcal{X}}'={\mathcal{X}}_+$ and ${\mathcal{X}}'={\mathcal{X}}_-$ both reach the bound.$\square$

From this lemma follows a bound for the conditional probability of an even smaller subset of ${\mathcal{X}}$, when the distribution has a nonzero trace distance to the uniform distribution. 