Abstract
In this paper a protocol for any two users to prove their identities to each other is proposed. The focus of this paper is to minimize the communication overhead and the key lengths without reducing the security. Our protocol achieves this goal by generalizing the Feig, Fiat, Shamir identification protocol. We prove it is secure based on the intractability of factoring random Blum integers.