Communication-efficient anonymous group identification
Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano · 1998
Identification schemes allow a user to identify herself to a verifying authority in a secure way (i.e., without revealing her secret key). Group identification schemes allow a user to identify herself as a member of a group of users in a secure and anonymous way (i.e., without revealing her identity nor her secret key). Several identification schemes and group identification schemes have been proposed in the literature. In this paper we consider the problem of constructing communication-efficient group identification schemes. Assuming factoring Blum integers is hard, we construct a secure and anonymous group identification scheme having communication complexity \\Theta(m+n), where m is the size of the group and n is the security parameter (previous results achieved complexity \\Theta(mn)). In fact, we show our protocol to be perfect zero-knowledge. We extend this scheme to the case of groups of t ? 1 users and obtain a protocol that improves on the communication complexity of previous ...