Paper 2019/1416

The Signal Private Group System and Anonymous Credentials Supporting Efficient Verifiable Encryption

Melissa Chase, Trevor Perrin, and Greg Zaverucha


In this paper we present a system for maintaining a membership list of users in a group, designed for use in the Signal Messenger secure messaging app. The goal is to support \(\mathit{private}\) \(\mathit{groups}\) where membership information is readily available to all group members but hidden from the service provider or anyone outside the group. In the proposed solution, a central server stores the group membership in the form of encrypted entries. Members of the group authenticate to the server in a way that reveals only that they correspond to some encrypted entry, then read and write the encrypted entries. Authentication in our design uses a primitive called a keyed-verification anonymous credential (KVAC), and we construct a new KVAC scheme based on an algebraic MAC, instantiated in a group \(\mathbb{G}\) of prime order. The benefit of the new KVAC is that attributes may be elements in \(\mathbb{G}\), whereas previous schemes could only support attributes that were integers modulo the order of \(\mathbb{G}\). This enables us to encrypt group data using an efficient Elgamal-like encryption scheme, and to prove in zero-knowledge that the encrypted data is certified by a credential. Because encryption, authentication, and the associated proofs of knowledge are all instantiated in \(\mathbb{G}\) the system is efficient, even for large groups.

Note: See the related blog post at

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. ACM CCS 2020
secure messagingsecure group messaginganonymous credentialsverifiable encryptionprivacy-preserving systems
Contact author(s)
melissac @ microsoft com
trevp @ signal org
gregz @ microsoft com
2020-11-10: last of 5 revisions
2019-12-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Melissa Chase and Trevor Perrin and Greg Zaverucha},
      title = {The Signal Private Group System and Anonymous Credentials Supporting Efficient Verifiable Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1416},
      year = {2019},
      doi = {10.1145/3372297.3417887},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.