International Association
for Cryptologic Research

The Signal protocol is a secure messaging protocol providing end-to-end encrypted asynchronous communication. In this paper, we focus on a method capable of hiding membership information from the viewpoint of non group members in a secure group messaging (SGM) protocol, which we call "membership privacy''. Although Chase et al. (ACM CCS 2020) have considered the same notion, their proposal is an extension of Signal so called "Pairwise Signal'' where a group message is repeatedly sent over individual Signal channels. Thus their protocol is not scalable. In this work, we extend the Cohn-Gordon et al. SGM protocol (ACM CCS 2018), which we call the Asynchronous Ratcheting Trees (ART) protocol, to add membership privacy. We employ a key-private and robust public-key encryption (Abdalla et al., TCC2010/JoC2018) for hiding membership-related values in the setup phase. Furthermore, we concentrate on the fact that a group common key provides anonymity. This fact is used to encrypt membership information in the key update phase. Our extension does not affect the forward secrecy and post-compromise security of the original ART protocol. Although the efficiency of each user in the setup phase is worsened, the setup phase is run only once, and it seems to be acceptable. Any additional cost for key update does not depend on the number of group members (specifically, one encryption and decryption of a symmetric key-encryption scheme and one execution of a key-derivation function for each key update are employed). Therefore, the proposed protocol can add membership privacy to the ART protocol with a quite small overhead.