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 