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

Melissa Chase; Trevor Perrin; Greg Zaverucha

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 $private$ $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 of prime order. The benefit of the new KVAC is that attributes may be elements in , whereas previous schemes could only support attributes that were integers modulo the order of . 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 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 messaging secure group messaging anonymous credentials verifiable encryption privacy-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: 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},
      url = {https://eprint.iacr.org/2019/1416}
}