The potential harm to privacy stemming from the use of data processing systems has been understood since computers were first applied to organize personal information. David Chaum’s seminal paper demonstrated the potential of cryptographic protocols to provide services such as user authentication and resource control while maintaining anonymity, reducing the need to distribute personal information or user passwords to remote servers.
In 1991, Chaum and van Heyst introduced the notion of group signatures. These cryptographic primitives provide revocable anonymity – in other words, the privacy of specific transactions can be revoked for legitimate reasons, mitigating tensions between system security and user privacy concerns. For these reasons, group signatures are considered one of the most flexible and promising cryptographic primitives for privacy.
Until recently, all known practical group signature schemes were based on RSA-type constructions. However, anonymous transactions that cross organization boundaries are facilitated by the use of discrete logarithm-type constructions. (In the e-cash setting, this was demonstrated by the Stefan Brands system.) In this talk, I describe the first group signature scheme based on the discrete logarithm problem.