Abstract

In identification protocols with public verifier coins (like Fiat-Shamir), a passive adversary watching the communication gains information intended only for the verifier. On the other hand, private coin protocols with fewer than three rounds cannot be zero-knowledge. In this paper, we introduce the notion of bounded-prover zero-knowledge proofs which require only two rounds and can be considered perfectly zero-knowledge under certain intractibility assumptions. Specifically, we exploit the gap between two computational problems to achieve zero-knowledge in a dishonest verifier scenario. Our example is based on the apparant intractibility of the Linear Diffie-Hellman Problem in bilinear maps. As a natural extension of the single user identification, we present the concept of ‘all or none’ group identification protocol that can be used to authenticate together an arbitrary number of users in a batch. We also present some extensions of our scheme.