An introduction to the theory of unconditionally secure message authentication using the constructive cryptography framework

We provide an introduction to certain ideas from the theory of unconditionally secure message authentication. We explain the notions of impersonation and substitution attacks, and explain how protection against these two types of attack implies composable, information theoretic security. We explain the relation of authentication protocols to universal hashing. We give both probabilistic and explicit constructions proving the existence of one way authentication protocols using a short secret key and we prove matching lower bounds on the required secret key size.

Then, we turn attention to interactive authentication protocols. We explain the message size reduction technique used by Gemmell and Naor and later Naor, Segev and Smith, and how it leads to protocols with secret key size independent of the message length. We also prove a matching lower bound on the secret key entropy. We generalize the lower bound proof of Naor, Segev and Smith and remove the assumption that the message is revealed in the first flow of the protocol.