Poster: Committee Moderation on Encrypted Messaging Platforms^††thanks: This work was supported by NSF grant 1814753.

Over the past decade, the increased prevalence of mobile computing and a growing desire for privacy have lead to a surge in the use of encrypted messaging services like WhatsApp, Facebook Messenger, and Signal. The deniability, anonymity, and security provided by these services are crucial to their widespread adoption, but by construction, these properties make it impossible to hold users accountable for the messages they send. With no accountability, these platforms are ripe for abuse, and WhatsApp group chats have been used to spread misinformation that has influenced elections [1, 2] and even incited the murder of a woman in India [3]. With no way of identifying or verifying the senders of these messages, little can be done.

Previous works [4, 5] have attempted to find a middle ground between accountability and privacy by allowing a moderator to verify the original sender of a message if the message is reported; if not reported, messages maintain all security guarantees. However, these works concentrate all responsibility for determining if a message requires moderation to a single party. This is undesirable. Using primitives from threshold cryptography, this work extends the message-reporting protocol Hecate [4] to a setting in which consensus among a group of moderators is required to reveal and verify the identity of a message’s sender.

An obvious road to accountability is to require users to sign their messages, but this completely destroys deniability, which is an important feature in many use cases. [5] preserve deniability by using a cryptographic primitive that allows signatures to be verified only by one person who is chosen at the time of signing. By making the designated verifier a trusted third party (for example, law enforcement or a school principal) and attaching to each message a zero-knowledge proof that the signature is valid, users can be confident that abusive messengers can be held accountable for the messages they send while still preserving deniability against everyone else. However, this protocol uses heavy crypto machinery and is quite expensive.

More recent work by [4] introduced a protocol called Hecate that provides the same security guarantees as [5] but is significantly cheaper in terms of the number of invocations of cryptographic primitives. It works as follows: In advance of sending any messages, users request “tokens” from a moderator containing (among other things) an encryption of the message-sender’s identity,

and a single-use ephemeral key pair $(pk_{eph},sk_{eph})$. The token also includes a signature $\sigma_{mod}$ made with the moderators private key that binds the key pair to $x_{1}$.

When a user sends a message, he consumes a token and attaches the signature

to the message along with the original moderator token. The signature binds $x_{1}$ to the sent message, and this metadata is carried with the message throughout its entire forwarding chain. If the message is ever reported, the moderator decrypts $x_{1}$ with her private key to obtain the original sender’s identity. To everyone else, the token provides no information.

We direct readers to [4] for a richer description of the protocol and its properties.

Our modified protocol retains the same general flow of token-issuing and message reporting from Hecate [4], but modifies the process by which $x_{1}$ is created and decrypted. We call our new protocol Cerberus (the name of the multi-headed dog that guards the river Styx) as a nod to the multiple moderators in the protocol and the greek name of the original Hecate protocol.

In Cerberus, there are $n$ moderators, and $k$ of them must cooperate to recover $id_{src}$ from $x_{1}$. (These $k$ and $n$ values are tunable protocol parameters.) The token-creation process is described below using Elgamal threshold encryption and the FROST [6] signature algorithm, although different threshold schemes could be substituted. In \CallCreateToken, $G$ is a (secure) group of order $q$ with generator $g$, the moderators’ public encryption key is $pk_{mod}$, and the corresponding private encryption key is divided into shares $s_{1},\ldots,s_{n}$ using a Shamir secret-sharing scheme [7]. The token generated by \CallCreateToken is identical to a token in the Hecate protocol [4], and the message is processed as is described in that paper.

To report a message, a user sends out requests to every moderator, each of whom decides individually whether or not to respond with a decryption share $d_{i}$ serving as a vote that the message should be acted upon. If more than $k$ decryption shares are received, i.e., if more than $k$ moderators believe that the message requires moderation, then one can recover the identity of the sender, $id_{src}$. If there are insufficient responses, $id_{src}$ remains hidden. This process of “voting” adresses the question posed in [4] of how to handle reported messages that are not necessarily abusive or misinfirmative. A formal description is as follows:

[4] includes an implementation and benchmark of the whole message cycle, so we focus on the modified portions of the protocol: token creation and message reporting. We implement these steps in Rust and run each party in a separate Linux container communicating over HTTP. Source code and more details are available on github [8]. Cerberus is much slower to create tokens than Hecate (on the order of 50x), but this isn’t a huge surprise: the benchmarks were run on slower hardware, and the distributed nature of this protocol involves a multitude of verification, serialization, and communication steps that are not required in Hecate. With that said, the operational costs of implementing a protocol such as this are still well within the budgetary constraints of a large company like Facebook. Extending the analysis in [4], we estimate the total cost of running all necessary servers to be under $100 a day for the entirety of WhatsApp.