---
abstract: |
    Information-theoretically secure (ITS) authentication is needed in Quantum Key Distribution (QKD). In this paper, we study security of an ITS authentication scheme proposed by Wegman&Carter, in the case of partially known authentication key. This scheme uses a new authentication key in each authentication attempt, to select a hash function from an Almost Strongly Universal$_2$ hash function family. The partial knowledge of the attacker is measured as the trace distance between the authentication key distribution and the uniform distribution; this is the usual measure in QKD. We provide direct proofs of security of the scheme, when using partially known key, first in the information-theoretic setting and then in terms of witness indistinguishability as used in the Universal Composability (UC) framework. We find that if the authentication procedure has a failure probability ${\varepsilon}$ and the authentication key has an ${\varepsilon}'$ trace distance to the uniform, then under ITS, the adversary’s success probability conditioned on an authentic message-tag pair is only bounded by ${\varepsilon}+|{\mathcal{T}}|{\varepsilon}'$, where $|{\mathcal{T}}|$ is the size of the set of tags. Furthermore, the trace distance between the authentication key distribution and the uniform increases to $|{\mathcal{T}}|{\varepsilon}'$ after having seen an authentic message-tag pair. Despite this, we are able to prove directly that the authenticated channel is indistinguishable from an (ideal) authentic channel (the desired functionality), except with probability less than ${\varepsilon}+{\varepsilon}'$. This proves that the scheme is (${\varepsilon}+{\varepsilon}'$)-UC-secure, without using the composability theorem.

    , Strongly Universal hash functions, Partially known key, Trace distance, Universal Composability, Quantum Key Distribution.
author:
- 'Aysajan Abidin and Jan-[Å]{}ke Larsson'
bibliography:
- 'wca.bib'
title: |
    Direct Proof of Security of Wegman-Carter\
    Authentication with Partially Known Key
---

Introduction {#sec:introduction}
============

Information-theoretically secure (ITS) message authentication codes [@WC1; @WC2] provide two users, Alice and Bob, with means to guarantee authenticity and integrity of messages exchanged over an insecure public channel. To achieve ITS (sometimes called unconditional security) the schemes used need shared secret between Alice and Bob. This procedure is secure against any adversary, even with unlimited computing and storage capability, provided that the key is perfectly secret. Such schemes normally have high demand for fresh secret key material, but even so they are used in some cryptographic schemes; especially in ITS key agreement schemes such as Quantum Key Distribution (QKD) [@BB84; @Ekert91]. QKD needs ITS authentication in order to thwart man-in-the-middle attacks [@BB84; @AL09; @Abidin; @PAL12].

This paper addresses security of an ITS Authentication scheme originally proposed by Wegman and Carter [@WC2], in the case of partially known key. The scheme is based on secretly selecting a function from a certain family of functions, details will be given in what follows. The function is then used to create a message authentication code, a tag, from the message. The important property of the family in question is that revealing the output, the tag, from one single use of a function does not reveal too much information on which function is used. This is to prohibit an attacker from identifying the function used, to generate a tag for another (forged) message. However, revealing two tags for two different messages may reveal enough to generate a tag for a third, so the function cannot be reused. Several messages can be authenticated securely by secretly selecting a new function for each desired authentication; we will refer to this mode of operation as WCA. Another is to hide the output, by encrypting the tag using one-time pad encryption, but in this paper, we only consider the WCA scheme.

The WCA scheme is ITS provided that the authentication key is uniformly distributed (or perfect). In practice, however, cryptographic keys are imperfect if partial information has leaked about them. One example of this is QKD-generated keys, where an eavesdropper can extract some information on the key, tightly restricted by security parameters of the system. In this paper, we study security of the WCA scheme in the scenario where the key is partially known to the adversary. We measure the adversary’s partial knowledge of the key as the trace distance between the distribution of the key and the uniform distribution, as is done in QKD. We should stress that our analysis is not just restricted to QKD. The same analysis applies *whenever* the authentication scheme under study is used with a key that has a small but non-zero trace distance to the uniform.

Related work, and contribution of this paper {#related-work-and-contribution-of-this-paper .unnumbered}
--------------------------------------------

The security of the WCA scheme as used in QKD was studied in [@CL] where the observation was made that, for the WCA scheme with partially known authentication key, an active attack is not always needed to weaken the system. The attacker can, in essence, wait for a beneficial moment and only launch an active (guessing) attack at that moment. The paper also proposes a countermeasure to this that is simple to implement.

A more recent paper [@Portmann] extends the security of the WCA scheme to the Universally Composable (UC) framework, proving that the scheme is UC-secure if the authentication key is perfectly secret. In the same paper, the Composability Theorem [@Canetti] is used to further extend the result to the case with partially known key, but due to the complexity of the UC framework and the composability theorem, the existence of the guessing attack mentioned above, and ultimately the differences between questions of Confidentiality and Integrity, there has been some discussion as to the meaning and appropriate statement of this result [@OH12; @RR12; @HY12].

In this paper, we aim to resolve the issue by providing upper bounds for failure probability, both for the problem discussed in [@CL] and for witness indistinguishability as used in the UC framework. This is done for the case of partially known key using a direct proof, without using the Composability Theorem. We first show that, if the authentication procedure has a failure probability ${\varepsilon}$; the authentication key has an ${\varepsilon}'$ trace distance to the uniform; and the adversary has seen a valid message-tag pair, then the adversary’s success probability of breaking the authentication is only bounded by ${\varepsilon}+|{\mathcal{T}}|{\varepsilon}'$, where $|{\mathcal{T}}|$ is the size of the tag space. This is *significantly* larger than what one would expect from the bound emerging from the UC framework. Despite this, we are able to prove directly that the authenticated channel is distinguishable from an authentic channel (the desired functionality) with probability less than ${\varepsilon}+{\varepsilon}'$.

The structure of the paper is as follows. Some background on Universal hashing and its use in constructing ITS authentication will be given in Section \[sec:background\]. In Section \[sec:trace-distance\], we present some properties of subset probability from distributions at nonzero trace distance from the uniform, that are needed in the security proofs. The ITS security bound of the scheme when using partially known key is proved in Section \[sec:ITS-security\], and the implications of the high bound is discussed at the end of the section. In Section \[sec:UC-security\], we prove indistinguishability of the scheme from the ideal functionality when using partially known key. Section \[sec:conclusions\] concludes the paper.

Background {#sec:background}
==========

In this section we present some necessary background that facilitates understanding of the whole paper. First of all, we need to specify the measure of partial knowledge to be used.

This is also known as the variational distance or the statistical distance between two probability distributions $P_X$ and $P_X'$, and is $$\label{eq:trace-distance}
  {\delta}(P_X,P_X') = \tfrac12\sum_{x\in{\mathcal{X}}}|P_X(x)-P_X'(x)|.$$

When we discuss security of a key in this paper, the following notion will be used.

\[def:key-security\] A key $k$ is called *perfect* if it is uniformly distributed from the adversary’s point of view; a key $k$ is called *${\varepsilon}$-perfect*, if its distribution has an ${\varepsilon}$ trace distance to the uniform.

The family of functions used to create the tags are defined as follows. Let ${\mathcal{M}}$ be the set of messages and ${\mathcal{T}}$ be the set of tags, both finite and ${\mathcal{T}}$ typically much smaller than ${\mathcal{M}}$. Also, let ${\mathcal{H}}$ be a set of functions from ${\mathcal{M}}$ to ${\mathcal{T}}$. The appropriate set of functions to use in ITS authentication is the following.

The set ${\mathcal{H}}$ is a *Strongly Universal$_2$ (SU$_2$) hash function family* if **(a)** for any $m_1\in{\mathcal{M}}$ and any $t_1\in{\mathcal{T}}$ there exist exactly $|{\mathcal{H}}|/|{\mathcal{T}}|$ hash functions $h\in{\mathcal{H}}$ such that $h(m_1)=t_1$, and **(b)** for any $m_2\in{\mathcal{M}}$ (distinct from $m_1$) and any $t_2\in{\mathcal{T}}$ (possibly equal to $t_1$), the fraction of those functions such that $h(m_2)=t_2$ is $1/|{\mathcal{T}}|$. If the fraction in (b) instead is at most ${\varepsilon}$, the family ${\mathcal{H}}$ is *${\varepsilon}$-Almost Strongly Universal$_2$ (${\varepsilon}$-ASU$_2$)*.

When proving security of an authentication scheme, there are two probabilities to bound: the probability of success in an *impersonation* attack, and the probability of success in a *substitution* attack. In an impersonation attack, the adversary pretends to be a legitimate user and tries to generate the correct tag for a (forged) message with no additional information, as would be given by a valid message-tag pair. In a substitution attack, the adversary intercepts a valid message-tag pair and tries to replace it with a new message-tag pair. This latter attack is more powerful than the former [@Johansson1].

It is fairly straightforward to see that ${\varepsilon}$-ASU$_2$ hash functions can be used to construct unconditionally secure authentication schemes in a natural way. Let Alice and Bob share a secret key $k$ to identify a hash function $h_k$ in a family ${\mathcal{H}}$ of ${\varepsilon}$-ASU$_2$ hash functions from ${\mathcal{M}}$ to ${\mathcal{T}}$. Alice sends her message $m$ along with $t=h_k(m)$ to Bob. Upon receiving $m$ and $t$, Bob verifies the authenticity of $m$ by comparing $h_k(m)$ with $t$. If $h_k(m)$ and $t$ are identical, then Bob accepts $m$ as authentic; otherwise, $m$ will be rejected.

Now, if Eve tries to impersonate Alice and sends $m^\prime$ without knowing the key $k$, or $h_k$, the best she can do is to guess the correct tag for $m^\prime$. The probability of success in this case is $1/|{\mathcal{T}}|$. Even if Eve waits until seeing a valid message-tag pair $(m,t)$ from Alice, the probability of guessing the correct tag $t'$ for $m^\prime$ is at most ${\varepsilon}$; cf. Def. 3(b). In other words, even seeing a valid message-tag pair does not increase Eve’s success probability above ${\varepsilon}$. Therefore, by using a family of ${\varepsilon}$-ASU$_2$ hash functions with suitably chosen ${\varepsilon}$, one can achieve unconditionally secure message authentication.

In this scheme, however, a key cannot be used more than once, because a repeated use of the same key may give Eve enough information to forge a valid message-tag pair; Def. 3 does not say anything about set sizes for three message-tag pairs. Therefore, in the mode of operation considered here, WCA, a new secret key is used for each authentication. The key length for typical known families of ${\varepsilon}$-ASU$_2$ hash functions is logarithmic in the message length $\log|{\mathcal{M}}|$ [@Stinson1; @Stinson2; @Stinson3; @Stinson4; @AticiStinson; @Hugo; @Hugo1; @Johansson; @Johansson1; @Boer; @AL11], where $\log$ denotes the binary 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. We will use this later when discussing security with preexisting partial knowledge and additional gained knowledge in the message exchange.

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

The conditional probability can be written $$\label{eq:sss2}
\begin{aligned}
  P_X({\mathcal{X}}''\,|\,{\mathcal{X}}') &= \frac{P_X({\mathcal{X}}'')}{P_X({\mathcal{X}}')} 
  = \frac{P_X({\mathcal{X}}'')}{P_X({\mathcal{X}}'') + P_X({\mathcal{X}}'\setminus{\mathcal{X}}'')}
  = \left(1+\frac{P_X({\mathcal{X}}'\setminus{\mathcal{X}}'')}{P_X({\mathcal{X}}'')}\right)^{-1}.
\end{aligned}$$ To bound this from above, we need an upper bound for $P_X({\mathcal{X}}'')$ and a lower bound for $P_X({\mathcal{X}}'\setminus{\mathcal{X}}'')$, both of which can be obtained using Lemma \[lemma:subset\], $$\label{eq:sss3}
    P_X({\mathcal{X}}'')\le \frac{|{\mathcal{X}}''|}{|{\mathcal{X}}|} + {\varepsilon};\quad
  P_X({\mathcal{X}}'\setminus{\mathcal{X}}'') \ge \frac{|{\mathcal{X}}'\setminus{\mathcal{X}}''|}{|{\mathcal{X}}|}
  - {\varepsilon}.$$ These give us the upper bound $$\label{eq:sss5}
\begin{aligned}
  P_X({\mathcal{X}}''\,&|\,{\mathcal{X}}')
  = \left(1+\frac{P_X({\mathcal{X}}'\setminus{\mathcal{X}}'')}{P_X({\mathcal{X}}'')}\right)^{-1} 
  \le\left(1+\frac{\frac{|{\mathcal{X}}'\setminus{\mathcal{X}}''|}{|{\mathcal{X}}|} -
      {\varepsilon}}{\frac{|{\mathcal{X}}''|}{|{\mathcal{X}}|} + {\varepsilon}} \right)^{-1} =
  \frac{|{\mathcal{X}}''|}{|{\mathcal{X}}'|} + \frac{|{\mathcal{X}}|}{|{\mathcal{X}}'|}{\varepsilon}.
\end{aligned}$$ Similarly, from Lemma \[lemma:subset\] we also know that $$\label{eq:sss6} 
  P_X({\mathcal{X}}'')\ge\frac{|{\mathcal{X}}''|}{|{\mathcal{X}}|} - {\varepsilon};\quad
  P_X({\mathcal{X}}'\setminus{\mathcal{X}}'') \le \frac{|{\mathcal{X}}'\setminus{\mathcal{X}}''|}{|{\mathcal{X}}|} 
  + {\varepsilon}.$$ These give us the lower bound $$\label{eq:sss8}
\begin{aligned}
  P_X({\mathcal{X}}''\,&|\,{\mathcal{X}}') = \left(1+\frac{P_X({\mathcal{X}}'\setminus{\mathcal{X}}'')}
    {P_X({\mathcal{X}}'')}\right)^{-1} 
  \ge\left(1+\frac{\frac{|{\mathcal{X}}'\setminus{\mathcal{X}}''|}{|{\mathcal{X}}|} + {\varepsilon}}
    {\frac{|{\mathcal{X}}''|}{|{\mathcal{X}}|} - {\varepsilon}} \right)^{-1} =
  \frac{|{\mathcal{X}}''|}{|{\mathcal{X}}'|} - \frac{|{\mathcal{X}}|}{|{\mathcal{X}}'|}{\varepsilon}.
\end{aligned}$$ This proves the inequality. The bound can be reached in several ways, for example when $({\mathcal{X}}_+\cup{\mathcal{X}}_-)\subseteq{\mathcal{X}}'$ and ${\mathcal{X}}''={\mathcal{X}}_+$.$\square$

Using the above theorem, we can derive a bound for the trace 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 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 increases if she sees a valid message-tag pair $(m,t=f_K(m))$. Eve’s gain will now depend on $m$, and her gain is maximal if both $f_{k_+}(m)=t$ and $f_{k_-}(m)=t$ for all $k_-\in{\mathcal{K}}_-$, so that $$\Pr\big\{f_{K}(m) =t\big\}
  =\frac{|{\mathcal{K}}|}{|{\mathcal{T}}|}\frac1{|{\mathcal{K}}|}+{\varepsilon}'
  -|{\mathcal{K}}_-|{\varepsilon}'\frac1{|{\mathcal{K}}_-|}
  =\frac1{|{\mathcal{T}}|}.$$ If ${\varepsilon}'$ is small, there will exist such messages $m$. Since the hash function family is SU$_2$, $|\{k:f_k(m_{\text E})=t_{\text E}\wedge{}f_k(m)=t\}|=|{\mathcal{K}}|/|{\mathcal{T}}|^2$, and again this set contains $k_+$ but excludes ${\mathcal{K}}_-$. Therefore $$\begin{split}
    \Pr\big\{f_{K}(m_{\text E})=t_{\text E}\,\big|\, f_{K}(m)=t\big\}
      &=\frac{\Pr\big\{f_{K}(m_{\text E})=t_{\text E}\wedge f_{K}(m)=t\big\}}
      {\Pr\big\{f_{K}(m)=t\big\}}\\
      &=\frac{\frac{|{\mathcal{K}}|}{|{\mathcal{T}}|^2}\frac1{|{\mathcal{K}}|}+{\varepsilon}'}{\frac1{|{\mathcal{T}}|}}
      =\frac{\frac1{|{\mathcal{T}}|^2}+{\varepsilon}'}{\frac1{|{\mathcal{T}}|}}
      =\frac1{|{\mathcal{T}}|}+|{\mathcal{T}}|{\varepsilon}'.
  \end{split}
  \label{eq:1}$$ Note that this is an equation, not an inequality. Before seeing $(m,t)$ Eve’s probability of a successful message insertion attack equals $1/|{\mathcal{T}}|+{\varepsilon}'$. After seeing $(m,t)$, Eve’s probability of a successful substitution attack *equals* $1/|{\mathcal{T}}|+|{\mathcal{T}}|{\varepsilon}'$.

This might be taken as cause for alarm, but one should note that this is message-dependent: not all message-tag pairs $(m,t)$ will cause such an increase. It was pointed out already in [@CL] that the message and used key value may be such that Eve may have this unexpectedly high probability of success. On the other hand, in some situations (here, when $f_{k_+}(m)\neq t$), Eve will instead find out that her most likely key value was, in fact, not used, and that she must remove it from the set of possible key values. In this case, the information she had becomes unusable; she will have lost information. But, importantly, Eve can find out if there was a gain or not, before performing an active (guessing) attack, by using her distribution of $K$ and the received message-tag pair from Alice. Eve then only performs an active attack if her success probability has increased (sufficiently, see [@CL]). From Alice’s point of view, the probability of having her message-tag pair *and* a successful attack from Eve is $1/|{\mathcal{T}}|+{\varepsilon}'$, but this probability is *per round*, not per guess (by Eve). Eve does not need to reveal herself by guessing frequently; she can wait for the beneficial case where her success probability is high [@CL].

Therefore, there is a clear need for an upper bound for the success probability in this situation. For general ${\varepsilon}$-ASU$_2$-based authentication, the following theorem holds.

\[thm-WCA\] *(Bound for guessing probability with partially known key.)* Consider the WCA scheme based on ${\varepsilon}$-ASU$_2$ hashing. If the authentication key is ${\varepsilon}'$-perfect (as random variable $K$ to the adversary), the probability of a successful message insertion is bounded by $$\Pr\big\{f_K(m_{\text E})=t_{\text E}\big\}\le\frac1{|{\mathcal{T}}|}+{\varepsilon}'.$$ If in addition the adversary has access 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 framework (to be discussed below), the relevant figure of merit is the trace distance to the uniform distribution, and not the guessing probability as given above. And also the trace distance increases by the same amount, in the beneficial case for Eve. The key is still random to Eve, but the distribution conditioned on her new knowledge that $h_K(m)=t$ has a larger trace distance to the uniform. A uniform distribution conditioned on $h_K(m)=t$ would be constant at $|{\mathcal{T}}|/|{\mathcal{K}}|$ (the set of still possible keys has the size $|{\mathcal{K}}|/|{\mathcal{T}}|$), but in our example, if both $f_{k_+}(m)=t$ and $f_{k_-}(m)=t$ for all $k_-\in{\mathcal{K}}_-$, $$\label{eq:3}
  \begin{split}
    P_K(k_+\,|\,h_K(m)=t)&=\frac{\Pr\{K=k_+\wedge
      h_K(m)=t\}}{P\{h_K(m)=t\}}
    =\frac{P_K(k_+)}{\Pr\{h_K(m)=t\}}\\
   &=\frac{\frac1{|{\mathcal{K}}|}+{\varepsilon}'}{\frac1{|{\mathcal{T}}|}}
    =\frac{|{\mathcal{T}}|}{|{\mathcal{K}}|}+|{\mathcal{T}}|{\varepsilon}'.
  \end{split}$$ This forces the conditional distribution of the key to have a high trace distance to the uniform. As before, the example gives the worst-case scenario, and an upper bound for this trace distance is given by the following theorem.

\[thm-WCA-cor\] *(Bound for trace distance with partially known key.)* Consider the WCA scheme based on ${\varepsilon}$-ASU$_2$ hashing. If the authentication key is ${\varepsilon}'$-perfect (as random variable $K$ to the adversary), and the adversary has access to a valid message-tag pair $(m,t)$, then the trace distance from the conditional probability to the uniform is 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, we use the indistinguishability notion to prove that, despite the substantially high bound for ITS, the WCA scheme with an ${\varepsilon}'$-perfect key is indistinguishable from the ideal authentication, except with probability ${\varepsilon}+{\varepsilon}'$. As a natural consequence, Universally Composable (UC) security of the WCA scheme with an ${\varepsilon}'$-perfect key directly follows from our proof of indistinguishability.

(-2.6,0) node\[fill=black!10,minimum width=2cm,minimum height=.8cm\]; (2.6,0) node\[fill=black!10,minimum width=2cm,minimum height=.8cm\]; (-3,0) node\[draw,minimum width=1cm,fill=white\](a) [Alice]{}; (3,0)node\[draw,minimum width=1cm,fill=white\](b) [Bob]{}; (0, 0)node\[draw,minimum width=3cm,fill=white\](f) [${\mathcal{F}}$]{}; (a) to node\[above\][$m$]{} (f); ($(f.south)+(-1,0)$) to\[bend right=45\] node\[below left\][$m$]{} ++(.5,-.5); ($(f.south)+(-1,0)$)++(.5,-.5) to ++(1,0); ($(f.south)+(-1,0)$)++(.5,-.5)++(1,0) to\[bend right=45\] node\[below right\][$m'$]{} ($(f.south)+(1,0)$); (f) to node\[above\][$m,\bot$]{} (b);

(-2,0) node\[fill=black!10,minimum width=3cm,minimum height=.8cm\]; (2,0) node\[fill=black!10,minimum width=3.1cm,minimum height=.8cm\]; (-3,0) node\[draw,minimum width=1cm,fill=white\](a) [Alice]{}; (3,0)node\[draw,minimum width=1cm,fill=white\](b) [Bob]{}; (0, 1)node\[draw,rounded rectangle, minimum width=1.3cm\](k) [Key]{}; (-1,0)node\[draw,rectangle,minimum width=1cm,fill=white\](T) [TAG]{}; (1,0)node\[draw,rectangle,minimum width=1cm,fill=white\](V) [VRFY]{}; (0,.5) node\[draw,dotted,minimum width=3cm,minimum height=1.7cm\] +(1.2,.75)node[WCA]{}; (a) to node\[above\][$m$]{} (T); (T.south) to\[bend right=45\] node\[below left\][$(m,t)$]{} ++(.5,-.5); (T.south)++(.5,-.5) to ++(1,0); (T.south)++(.5,-.5)++(1,0) to\[bend right=45\] node\[below right\][$(m',t')$]{} (V.south); (V) to node\[above\][$m',\bot$]{} (b); (k.south) to node\[above right,at end\][$k$]{} (T.north); (k.south) to node\[above left,at end\][$k$]{} (V.north);

The ideal functionality of authentication, an *authentic* channel ${\mathcal{F}}$, connects Alice and Bob in such a way that Bob can be certain that any message output from the channel was sent by Alice. If the message was modified on the channel, the symbol $\bot$ is delivered, see Fig. \[fig:functionality\]. In other words, messages received from ${\mathcal{F}}$ are either authentic or blocked, and so *cannot* be successfully modified or substituted. Note that there is no confidentiality requirement, so the message can be read by anyone. The real implementation of authentication in the WCA scheme has three components, as depicted in Fig. \[fig:functionality\]: a tag generation algorithm TAG, a verification algorithm VRFY, and a key source. Both TAG and VRFY use the same key. From an input message $m$, Alice uses TAG to compute a message-tag pair $(m,t)$ where $t=f_k(m)$ and $f_k$ is a hash function from an ${\varepsilon}$-ASU$_2$ family identified by $k$. Bob uses VRFY to verify a received message-tag pair $(m',t')$, and VRFY outputs $m'$ if $f_k(m')=t'$ (for example if $m'=m$ and $t'=t$), otherwise $\bot$.

The distinguisher (in UC terminology, the *environment*) ${\mathcal{Z}}$ should not be able to distinguish the two systems, except with low probability. It can attempt to distinguish the two by controlling the input to the system (the message $m$), and the output from the channel $(m',t')$. The systems should be indistinguishable even under the presence of an *adversary* ${\mathcal{A}}$, and it is sufficient to consider the system under an adversary completely controlled by the environment [@Canetti], a *dummy adversary* that only forwards the desired channel output from the environment. As is, the systems are trivially distinguishable because of the lack of a tag in the ideal system. We therefore add a *simulator* ${\mathcal{S}}$ to the ideal functionality, that adds a tag $t$ that is generated from $m$ using the appropriate key and hash function to make it indistinguishable from the real case, and strips off any received tag $t'$ after the channel. The name simulator also alludes to simulating the adversary, and is especially simple when simulating the dummy adversary.

We now want to ensure that the environment ${\mathcal{Z}}$ cannot distinguish between the two cases *(a)* it is interacting with ${\mathcal{A}}$ and participants running the WCA scheme or *(b)* it is interacting with ${\mathcal{S}}$ and participants running ${\mathcal{F}}$, except with low probability (see Fig. \[fig:setup1\]). Perhaps we should point out that the description here differs slightly from that of [@Portmann]. The WCA scheme is resolved in somewhat finer detail and is separated from the participants, and the ideal functionality is that of an authentic channel rather than an immutable but blockable channel. This is done solely for the purpose of clear comparison of the real and the ideal cases, and does not affect the results of the security evaluation. Now, having set the stage, we can state our main theorem.

(0,-3) node\[draw,minimum width=6.5cm\] (z) [${\mathcal{Z}}$]{}; (-2.6,0) node\[fill=black!10,minimum width=2cm,minimum height=.8cm\]; (2.6,0) node\[fill=black!10,minimum width=2cm,minimum height=.8cm\]; (-3,0) node\[draw,minimum width=1cm,fill=white\](a) [Alice]{}; (3,0)node\[draw,minimum width=1cm,fill=white\](b) [Bob]{}; (0,-1.5)node\[draw,minimum width=3cm\](s) [${\mathcal{S}}$]{}; (0, 0)node\[draw,minimum width=3cm,fill=white\](f) [${\mathcal{F}}$]{}; (-2.8, -1.5)node\[draw,rounded rectangle, minimum width=1.3cm\](k) [Key]{}; (z.west) to\[bend left=40\] node\[right\][$m$]{} (a.west); (a) to node\[above\][$m$]{} (f); (k) to node\[above\][$k$]{} (s); ($(f.south)+(-1,0)$) to node\[left\][$m$]{} ($(s.north)+(-1,0)$); ($(s.south)+(-1,0)$) to node\[left\][$(m,t)$]{} ($(z.north)+(-1,0)$); ($(z.north)+(1,0)$) to node\[right\][$(m',t')$]{} ($(s.south)+(1,0)$); ($(s.north)+(1,0)$) to node\[right\][$m'$]{} ($(f.south)+(1,0)$); (f) to node\[above\][$m,\bot$]{} (b); (b.east) to\[bend left=40\] node\[left\] [$m',\bot$]{} (z.east);

(0,-3) node\[draw,minimum width=6cm\] (z) [${\mathcal{Z}}$]{}; (-2,0) node\[fill=black!10,minimum width=3cm,minimum height=.8cm\]; (2,0) node\[fill=black!10,minimum width=3.1cm,minimum height=.8cm\]; (-3,0) node\[draw,minimum width=1cm,fill=white\](a) [Alice]{}; (3,0)node\[draw,minimum width=1cm,fill=white\](b) [Bob]{}; (0,-1.5)node\[draw,minimum width=3cm\](e) [${\mathcal{A}}$]{}; (0, 1)node\[draw,rounded rectangle, minimum width=1.3cm\](k) [Key]{}; (-1,0)node\[draw,rectangle,minimum width=1cm,fill=white\](T) [TAG]{}; (1,0)node\[draw,rectangle,minimum width=1cm,fill=white\](V) [VRFY]{}; (0,.5) node\[draw,dotted,minimum width=3cm,minimum height=1.7cm\] +(1.2,.75)node[WCA]{}; (z.west) to\[bend left=40\] node\[right\][$m$]{} (a.west); (a) to node\[above\][$m$]{} (T); (T.south) to node\[left\][$(m,t)$]{} ($(e.north)+(-1,0)$); ($(e.south)+(-1,0)$) to node\[left\][$(m,t)$]{} ($(z.north)+(-1,0)$); ($(z.north)+(1,0)$) to node\[right\][$(m',t')$]{} ($(e.south)+(1,0)$); ($(e.north)+(1,0)$) to node\[right\][$(m',t')$]{} (V.south); (V) to node\[above\][$m',\bot$]{} (b); (b.east) to\[bend left=40\] node\[left\] [$m',\bot$]{} (z.east); (k.south) to node\[above right,at end\][$k$]{} (T.north); (k.south) to node\[above left,at end\][$k$]{} (V.north);

\[thm-WCA-uc\] *(Indistinguishability)* No distinguisher ${\mathcal{Z}}$ can distinguish between the two cases

*(a)* it is interacting with ${\mathcal{A}}$ and participants running the WCA scheme based on ${\varepsilon}$-ASU$_2$ hashing using ${\varepsilon}'$-perfect authentication key, or

*(b)* it is interacting with ${\mathcal{S}}$ and participants running ${\mathcal{F}}$

except with probability ${\varepsilon}+{\varepsilon}'$.

In the proof, the message given to Alice is denoted $X$ and its distribution is in control of the environment ${\mathcal{Z}}$. The authentication key $K$ is used to select $f_K$ that in turn is used to generate the tag. The key distribution is not in control of ${\mathcal{Z}}$, and has ${\varepsilon}'$ trace distance to the uniform. The corresponding output message-tag pair is denoted $Y$. The channel output is denoted $Y'$ and is again in control of ${\mathcal{Z}}$. The output of the real and ideal functionality is denoted ${\widetilde{X}}$ and ${\widehat{X}}$, respectively and take values in ${\mathcal{M}}\cup\{\bot\}$. Thus, the environment ${\mathcal{Z}}$ has access to the joint random variables $XYY'{\widetilde{X}}$ in the real case and $XYY'{\widehat{X}}$ in the ideal case. In both cases, ${\mathcal{Z}}$ is in control of $X$ and $Y'$. The random variable $Y$ has an identical distribution (conditioned on the value of $X$) in both cases, so distinguishing the two systems can only be done from the output ${\widetilde{X}}$ or ${\widehat{X}}$, if the output is different from $X$ and also not $\bot$. This is only possible in the real implementation, and the probability of this is $\Pr\{{\widetilde{X}}\neq\bot\wedge{\widetilde{X}}\neq X\}$. This can also be studied through the trace distance between the two distributions $$\label{eq:trace-WCA}
    \begin{split}
      \delta(P_{XYY'{\widetilde{X}}},P_{XYY'{\widehat{X}}}) =
      \frac{1}{2}\sum_{m,y,y',x'}
      \Big|P_{XYY'{\widetilde{X}}}\big(m,y,y',x'\big)-
      P_{XYY'{\widehat{X}}}\big(m,y,y',x'\big)\Big|.
    \end{split}$$ Above, the index $x'$ runs over ${\mathcal{M}}\cup\{\bot\}$. Since the real and ideal cases are indistinguishable if $m=x'$, the above sum simplifies to the terms where $m\neq x'$. Furthermore, if $m\neq x'$ the ideal functionality ${\mathcal{F}}$ always outputs $\bot$. We can therefore change the name of the index to $m'$ since it now runs only over ${\mathcal{M}}$, and we find that the trace distance equals $\Pr\{{\widetilde{X}}\neq\bot\wedge{\widetilde{X}}\neq X\}$, because $$\label{eq:trace-WCA-2}
    \begin{split}
      \delta&(P_{XYY'{\widetilde{X}}},P_{XYY'{\widehat{X}}})= \sum_{m,y,y',m'\neq m}
      P_{XYY'{\widetilde{X}}}\big(m,y,y',m'\big)
      =\Pr\{{\widetilde{X}}\neq\bot\wedge{\widetilde{X}}\neq X\}\\
      &= \sum_{m,t,t',m'\neq m}       P_{X}(m)P_{Y|X}\big((m,t)|m\big)P_{Y'|XY}\big((m',t')\big|m,(m,t)\big)
      P_{{\widetilde{X}}|XYY'}\big(m'|m,(m,t),(m',t')\big)\\
      &= \sum_{m,t,t',m'\neq m}       P_{X}(m)\Pr\big\{h_K(m)=t\big\}P_{Y'|Y}\big((m',t')\big|(m,t)\big)
      \Pr\big\{h_K(m')=t'|h_K(m)=t\big\}\\
      &=\sum_{m,t,t',m'\neq m} P_{X}(m)       P_{Y'|Y}\big((m',t')\big|(m,t)\big)\Pr\{f_K(m')=t' \,\wedge\,
      f_K(m)=t\}.
    \end{split}$$ Now, the simple bound $\Pr\{f_K(m')=t'\,\wedge\,
  f_K(m)=t\}\le{\varepsilon}/|{\mathcal{T}}|+{\varepsilon}'$ (from Lemma \[lemma:subset\]) only gives $$\begin{split}
      \delta(P_{XYY'{\widetilde{X}}},P_{XYY'{\widehat{X}}})
      &=\sum_{m,t,t',m'\neq m} P_{X}(m)
      P_{Y'|Y}\big((m',t')|(m,t)\big)\Pr\{f_K(m')=t' \,\wedge\,
      f_K(m)=t\} \\
      &\le \sum_{m,t,t',m'\neq m}
      P_{X}(m) P_{Y'|Y}\big((m',t')|(m,t)\big)
      \Big(\frac{{\varepsilon}}{|{\mathcal{T}}|}+{\varepsilon}'\Big)={\varepsilon}+|{\mathcal{T}}|{\varepsilon}',
    \end{split}$$ and that is insufficient for our purposes. This occurs for the same reason as the high bounds in Theorems \[thm-WCA\] and \[thm-WCA-cor\]: the upper bound for the individual terms *is* this high, but the bound is not reached for all $(m,t)$. Here, we can do better by bounding the expression $$\sum_{t,t',m'\neq m}
    P_{Y'|Y}\big((m',t')|(m,t)\big)\Pr\{f_K(m')=t' \,\wedge\, f_K(m)=t\}$$ instead of the individual terms. The probability $P_{Y'|Y}\big((m',t')|(m,t)\big)$ corresponds to the adversary’s attack strategy: given a message-tag pair on the input to the channel, choose what to substitute as output from the channel. If the adversary uses a deterministic attack, meaning that $(m',t')$ are functions of $(m,t)$, we immediately obtain $$\begin{split}
      \sum_{t,t',m'\neq m}
      &P_{Y'|Y}\big((m',t')|(m,t)\big)\Pr\{f_K(m')=t'\,\wedge\,f_K(m)=t\}
      \\&
      = \sum_{t}\Pr\{f_K\big(m'(m,t)\big)=t'(m,t) \,\wedge\, f_K(m)=t\}\\
      &= \Pr\Big[\bigcup_t\big\{f_K\big(m'(m,t)\big)=t'(m,t) 
      \,\wedge\, f_K(m)=t\big\}\Big]\\
      &\le|{\mathcal{T}}|\Big({\varepsilon}\frac{|{\mathcal{K}}|}{|{\mathcal{T}}|}\Big)\frac1{|{\mathcal{K}}|}+{\varepsilon}_1
      ={\varepsilon}+{\varepsilon}_1.
    \end{split}$$ The sum can be rewritten as the probability of a union because the events are disjoint, and the inequality is obtained from Lemma \[lemma:subset\]. The remaining average over $m$ has no effect on the bound.

If the adversary has a randomized attack, we can introduce an auxiliary probability space $(\Omega,{\mathcal{F}},\mu)$ for the random variable $Y'=(X',T')$, where $\Omega$ is the sample space, ${\mathcal{F}}$ is the $\sigma$-algebra of events, and $\mu$ is the probability measure. Using the indicator function $\chi$ we can write $$P_{Y'|Y}\big((m',t')|(m,t)\big)
    =\int_\Omega\chi_{\{\omega\in\Omega:Y'(m,t,\omega)=(m',t')\}}(\omega)\,d\mu.$$ We note that for each fixed sample $\omega$, the attack is deterministic. The above approach now gives $$\begin{aligned}
    \sum_{t,t',m'\neq m}&
    P_{Y'|Y}\big((m',t')|(m,t)\big)\Pr\{f_K(m')=t' \,\wedge\, f_K(m)=t\}\\
    &\,=\sum_{t,t',m'\neq m}\int_\Omega\chi_{\{\omega\in\Omega:
      Y'(m,t,\omega)=(m',t')\}}(\omega)\,d\mu\Pr\{f_K\big(m'\big)
    =t' \,\wedge\, f_K(m)=t\}\\
    &\,=\int_\Omega\sum_{t}\Pr\big\{f_K\big(X'(m,t,\omega)\big)
    =T'(m,t,\omega) \,\wedge\, f_K(m)=t\big\}\,d\mu\\
    &\le \int_\Omega \,{\varepsilon}+{\varepsilon}'\,d\mu = {\varepsilon}+{\varepsilon}'.
  \end{aligned}$$ Again, the remaining average over $m$ has no effect on the bound.$\square$

Now, the UC security of the WCA scheme with a partially known key follows immediately.

\[cor-WCA-uc\] *(UC security)* Consider the WCA scheme based on ${\varepsilon}$-ASU$_2$ hashing. Assume that the authentication key $k$ is ${\varepsilon}'$-perfect. Then the WCA scheme is ${\varepsilon}+{\varepsilon}'$-UC-secure.

Conclusions {#sec:conclusions}
===========

We have presented a detailed security analysis of Wegman-Carter authentication with failure probability ${\varepsilon}$, in the case of partially known key whose distribution is ${\varepsilon}'$ trace distance from the uniform distribution. We proved tight upper bounds for the adversary’s success probability of breaking the scheme with impersonation and substitution attacks in the information-theoretic setting, with success probability upper bounded by $1/|{\mathcal{T}}|+{\varepsilon}'$ and ${\varepsilon}+|{\mathcal{T}}|{\varepsilon}'$, respectively. The latter is substantially higher than expected, but we give an example that reaches the bound, meaning that the bound is sharp. Also in terms of trace distance, a similar increase can be noted. The best possible upper bound to the trace distance after having seen a valid message-tag pair is $|{\mathcal{T}}|{\varepsilon}'$; the same example tells us that this bound is sharp.

Since the bounds we obtained are substantially higher than what one would expect, we also analyze whether the scheme is secure in terms of witness indistinguishability. Despite the high success probability bound and increase in trace distance, we prove that the authentication under study is indeed indistinguishable from the ideal functionality, except with probability less than ${\varepsilon}+{\varepsilon}'$. We provide a direct proof for the case of partially known key, without using the composability theorem. Naturally, UC security of the scheme with partially known key follows from our proof of indistinguishability.

These results seem to contradict each other, but they do not. The first should be understood as pointing out that the attacker will have high success probability in some rounds, after having seen a valid message-tag pair. The second shows that this happens seldom enough to retain the expected security. The important lesson is that the attacker can refrain from performing an active attack, if the success probability is low after having seen a valid message-tag pair. This is because she can calculate her success probability from available knowledge on the key and the additional information obtained from a valid message-tag pair. In essence she does not need to reveal herself at each attempt to break the system, but needs only take this risk when the success probability is high. The security parameters should not be read as “the probability that an attacker is revealed, in each attack” but rather “the probability that the system is broken, in each round.” It is important to keep this in mind when using this type of authentication, and of course, the size of the security parameters ${\varepsilon}$ and ${\varepsilon}'$ should be chosen accordingly.
