On Computationally Secure Authentication Tags Requiring Short Secret Shared Keys

As an application of strongly universal-2 classes of hash functions, Wegman and Carter have proposed a provably secure authentication tag system.1 Their technique allows the receiver to be certain that a message is genuine. An enemy, even one with infinite computing power, cannot forge or modify a message without detection. Moreover, there are no messages that just happen to be easy to forge. Unfortunately, their scheme requires that the sender and the receiver share a rather long secret key if they wish to use the system more than once. Indeed, the length of the key is essentially n log(1/p), where n is the number of messages they wish to be able to authenticate before having to agree on a new secret key, and p is the probability of undetected forgery they are willing to tolerate. Since they also proved that n log(1/p) is a lower bound on the number of bits required by any tag system that assures security against infinite computing power, it is clearly necessary to resort to computational complexity if we wish to have a scheme usable in practice allowing a potentially very large number of messages to be authenticated.