Cryptology ePrint Archive: Report 2019/1416

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

Melissa Chase and 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.

Category / Keywords: cryptographic protocols / secure messaging, secure group messaging, anonymous credentials, verifiable encryption, privacy-preserving systems

Date: received 9 Dec 2019, last revised 10 Dec 2019

Contact author: melissac at microsoft com,trevp@signal org,gregz@microsoft com

Available format(s): PDF | BibTeX Citation

Note: See the related blog post at

Version: 20191210:202255 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]