Provably secure session key distribution

We study session key distribution in the ting of Needham and Schroeder. (This is three-party setthe trust model assumed by the popular Kerberos "authentication system. ) Such protocols are basic building blocks for contemporary distributed systems-yet the underlying problem has, up until now, lacked a definition or provably-good solution, One consequence is that incorrect protocols have proliferated. This paper provides the first treatment of this problem in the complexity-theoretic framework of modern cryptography. We present a definition, protocol, and a proof that the protocol satisfies the definition, assuming the (minimal) assumption of a pseudorandom function. When this assumption is appropriately instantiated, our protocols are simple and efficient.