A Tale of Trees: Improving the Efficiency of Secure Group Messaging Protocols

While Secure Messaging protocols, used by widely known applications like WhatsApp and Signal, have reached a certain amount of maturity in terms of security and efficiency, their transposition to the group setting (with over tens of thousands of users) is still a new research topic. The IETF has released in July 2024 a new standard of Secure Group Messaging protocol called Messaging Layer Security (MLS), which is considered as the state-of-the-art in that field. The core subprotocol of MLS is a group key exchange mechanism named TreeKEM, which relies on a binary tree in order to carry out a handshake with a communication cost logarithmic in the number of users. However, that bandwidth highly depends on the tree structure, which is itself influenced by the group history. Therefore, the aimed logarithmic cost appears to be a lower bound that is rarely reached in practice.

In that context, I present you two works that aim to reduce the communication cost of a Secure Group Messaging protocol. Firstly, we have analyzed the impact of the tree structure of TreeKEM on its communication cost, and the way to keep that tree as close as possible to the optimal balance. Then, in order to further increase the efficiency of our protocol, we have designed a novel protocol architecture that offers significantly enhanced communication and storage performances compared to TreeKEM, using the fact that some group members are administrators with the ability to perform operations on the member group.