Paper 2019/1416

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

Melissa Chase, Trevor Perrin, and Greg Zaverucha

Abstract

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/

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Major revision. ACM CCS 2020
DOI
10.1145/3372297.3417887
Keywords
secure messagingsecure group messaginganonymous credentialsverifiable encryptionprivacy-preserving systems
Contact author(s)
melissac @ microsoft com
trevp @ signal org
gregz @ microsoft com
History
2020-11-10: last of 5 revisions
2019-12-09: received
See all versions
Short URL
https://ia.cr/2019/1416
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1416,
      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.