keywords: challenge-response protocols, protocol graph, entity authentication, reflection attack

abstract  In this paper, we address the problem of multi-party entity authen- tication. We prove that the lower bound on the number of messages of multi-party challenge-response protocols is 2n-1, where n is the num- ber of the participants of the protocol, and propose two protocols that achieve this lower bound. Our protocols are, thus, eÆcient in the sense that they use the minimum number of messages required to solve the multi-party entity authentication problem based on challenge-response principles.