An Exploration of Group and Ring Signatures
Sarah J Meiklejohn · 2011
Group signatures are a modern cryptographic primitive that allow a member of a specific group (e.g., “the White House staff ” or “employees of Corporation X that publish press releases”) to sign messages on behalf of the group as a whole; i.e., without revealing their individual identities and thus providing them with a certain degree of anonymity and privacy. They have quite a number of potential applications (and in fact have been incorporated into the latest version of the Trusted Platform Module, or TPM), and are still an active area of research. In this work, we explore group signatures and the many variations that have been considered since their original introduction in 1991 by Chaum and van Heyst. We furthermore discuss the basic primitives used to realize group signatures and their numerous definitions of security; we then outline a generic group signature construction (due to Bellare, Micciancio, and Warinschi) that achieves the strongest notion of security and give intuition for how it does this. As a complement to group signatures we also consider ring signatures, in which users can enjoy anonymity properties similar to those of group signatures but can form their groups in an adhoc manner; i.e., without any setup or consent required from the other members of these “ad-hoc groups, ” or rings. We again consider the different notions of security for ring signatures, as well as the different variations on the original concept introduced by Rivest, Shamir, and Tauman in 2001. We then outline a ring signature construction (due to Shacham and Waters) that achieves the strongest notion of security, and conclude with a discussion of open problems for both group and ring signatures. 1