Unconditionally secure entity authentication

An entity-authentication scheme is a two-party protocol by which a party in a distributed system confirms the identity of a communication partner. Bellare and Rogaway (1993) formulated this problem using a complexity theoretic framework. In this paper, we study entity-authentication in an information theoretic framework, where adversaries are infinitely powerful. We first modify the framework given by Bellare and Rogaway to an unconditionally secure setting. Communication between players is entirely controlled by an infinitely powerful adversary A. The adversary can deliver messages out of order and to unintended recipients, and can concoct messages of the adversary´s own choosing. What is more, the adversary can control who is attempting to authenticate whom. We then present a lower bound on the cheating probability and a lower bound on the size of keys for unilateral entity authentication protocols. That is, in each session, P _i authenticates P_j but P_j does not authenticate P_i. Finally, we show an entity authentication scheme which is proven to be secure and that meets all the equalities of our bounds