Abstract or Summary:
We present a series of protocols for authenticating an individual's membership in a group without revealing that individual's identity and without restricting how the membership of the group may be changed. In systems using these protocols a single message to the authenticator may be used by an individual to replace her lost key or by a trusted third party to add and remove members of the group. Applications in electronic commerce and communication can thus use these protocols to provide anonymous authentication while accommodating frequent changes in membership. We build these protocols on top of a new primitive: the verifiably common secret encoding. We show a construction for this primitive, the security of which is based on the existence of public-key cryptosystems capable of securely encoding multiple messages containing the same plaintext. Because the size of our construct grows linearly with the number of members in the group, we describe techniques for partitioning groups to improve performance.