Secure Group Messaging (SGM) protocols allow groups of users to asynchronously and securely communicate with each other. They have received significant attention recently, including in an effort by the IETF Messaging Layer Security (MLS) working group to standardize an eponymous protocol. In SGM protocols, users share group secrets across time to enable communications and are allowed to asynchronously perform group additions and removals. Moreover, they provide robust security guarantees regarding user state exposures: forward secrecy (FS) and post-compromise security (PCS). The former ensures that group secrets prior to state compromise remain secure, while the latter ensures that the users can recover from state compromise using normal protocol operations. However, the group key agreement primitive at the core of SGM protocols, Continuous Group Key Agreement (CGKA), which is achieved by the TreeKEM protocol in MLS, suffers from bad worst case efficiency and requires strong assumptions, due to asynchronous user operations.
We propose that in the common case of a group membership change policy which allows a single administrator to perform all group additions and removals, classical Multicast Key Agreement (MKA) may serve as a more efficient substitute for CGKA in SGM. In MKA protocols, an omniscient group manager performs all group operations, which increases efficiency and reduces assumptions. However, existing MKA schemes in the literature do not provide formal security analyses nor efficiency analyses regarding dynamically changing groups, and also lack FS and PCS.
We first present rigorous security definitions for MKA which provide increasing levels of security in the case of state exposure of both users and the group manager. We then construct an efficient and formally secure MKA protocol with dynamic groups. Finally, we provide a toy implementation of our protocol, and run experiments which show that the left-balanced binary tree structure used in TreeKEM can be substituted with red-black trees in MKA for better efficiency.