eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

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 https://signal.org/blog/signal-private-group-system/

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{https://eprint.iacr.org/2019/1416}},
      url = {https://eprint.iacr.org/2019/1416}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.