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 