Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Security and Efficiency of Secure Group Messaging Protocols

Guirec Lebrun

Published Dec 1, 2025• 0 citations
OpenAlex

Abstract

Secure Group Messagings are cryptographic protocols that allow safe group conversation within potentially large user groups. They are based on a dedicated type of group key exchange mechanism named Continuous Group Key Agreement (CGKA), which generates a continuously evolving group key in a safe and efficient way. Messaging Layer Security (MLS) is an IETF-standardized secure group messaging protocol which uses a protocol called TreeKEM as its CGKA.We study in this thesis the security and the efficiency of the CGKAs used within secure group messagings. Firstly, we propose a variant of TreeKEM (called Quarantined-TreeKEM) that solves a security issue related to inactive users, whose behavior prevents fundamental security properties to be fulfilled. Moreover, we improve the efficiency of TreeKEM, especially regarding its communication cost, by considering the best way to manage the tree graph used by that CGKA. Finally, we show that in the particular – yet common – use case where only a subset of users is granted the administration rights, we can design a new CGKA whose performances outperform those of regular decentralized CGKAs such as TreeKEM.This thesis thus aims to improve the state-of-the-art in secure group messaging protocols, in a context where strong security and energy sobriety are necessary features.

Related papers

Quarantined-TreeKEM: A Continuous Group Key Agreement for MLS, Secure in Presence of Inactive Users

Céline Chevalier, Guirec Lebrun, Ange Martinelli +1 more

The recently standardized secure group messaging protocol Messaging Layer Security (MLS) is designed to ensure asynchronous communications within large groups, with an almost-optimal communication cost and the same security level as point-to-point secure messaging protocols such as Signal. In particular, the core sub-protocol of MLS, a Continuous Group Key Agreement (CGKA) called TreeKEM, must generate a common group key that respects the fundamental security properties of post-compromise security and forward secrecy which mitigate the effects of user corruption over time

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Dec 2, 2024•3 citations

CGKA-FA: Secure and Flexible Group Key Agreement with Authentication Update

Kaisei Kajita, Keita EMURA, Kazuto Ogawa +2 more

Secure messaging (SM) protocols allow users to communicate securely over an untrusted infrastructure. Alwen et al. formally defined the key agreement protocol used in secure group messaging (SGM) as continuous group key agreement (CGKA) at CRYPTO 2020. In their CGKA protocol, all of the group members have the same rights to execute algorithms, and a trusted third party is needed. On the other hand, some applications such as a broadcasting service may have an administrator in the group. When the administrator as the group manager (GM) is distinguished from other group members, i.e., in a one-to-many setting, it would be better for the GM and the other group members to have different authorities. We propose a new CGKA protocol, called CGKA with flexible authorization (CGKA-FA) by incorporating a ratcheting digital signature scheme (Cremers et al. at USENIX Security 2021) into the existing CGKA protocol and demonstrate that such a simple modification allows us to provide flexible authorization. Our proposed protocol does not need an external public key infrastructure (PKI) functionality as a trusted third party. So no third party outside the group handles confidential information of users and thus no one except group members can read messages regardless of key updates. In our CGKA-FA protocol, it is possible to set privileges of users in a group flexibly, which is highly compatible with the field of broadcasting.

Journal of Information Processing•Jan 1, 2026•0 citations

Continuous Group Key Agreement with Flexible Authorization and Its Applications

Kaisei Kajita, Keita Emura, Kazuto Ogawa +2 more

Secure messaging (SM) protocols allow users to communicate se-curely over an untrusted infrastructure. Alwen et al. formally de-fined the key agreement protocol used in secure group messaging (SGM) as continuous group key agreement (CGKA) at CRYPTO 2020. In their CGKA protocol, all of the group members have the same rights and a trusted third party is needed. On the other hand, some SGM applications may have a user in the group who has the role of an administrator. When the administrator as the group manager (GM) is distinguished from other group members, i.e., in a one-to-many setting, it would be better for the GM and the other group members to have different authorities. We achieve this flex-ible authorization by incorporating a ratcheting digital signature scheme (Cremers et al. at USENIX Security 2021) into the existing CGKA protocol and demonstrate that such a simple modification allows us to provide flexible authorization. In Alwen et al.'s CGKA protocol, an external public key infrastructure (PKI) functionality as a trusted third party manages the confidential information of users, and the PKI can read all messages until all users update their own keys. In contrast, the GM in our protocol has the same role as the PKI functionality in the group, so no third party outside the group handles confidential information of users and thus no one except group members can read messages regardless of key updates. Our proposed protocol is useful in the creation of new applications such as broadcasting services.

ACM International Workshop on Security and Privacy Analytics (IWSPA)•Apr 6, 2023•4 citations

Key Agreement for Decentralized Secure Group Messaging with Strong Security Guarantees

Matthew Weidner, Martin Kleppmann, Daniel Hugenroth +1 more

Secure group messaging protocols, providing end-to-end encryption for group communication, need to handle mobile devices frequently being offline, group members being added or removed, and the possibility of device compromises during long-lived chat sessions. Existing work targets a centralized network model in which all messages are routed through a single server, which is trusted to provide a consistent total order on updates to the group state. In this paper we adapt secure group messaging for decentralized networks that have no central authority. Servers may still optionally be used, but they are trusted less. We define decentralized continuous group key agreement (DCGKA), a new cryptographic primitive encompassing the core of a decentralized secure group messaging protocol; we give a practical construction of a DCGKA protocol and prove its security; and we describe how to construct a full messaging protocol from DCGKA. In the face of device compromise our protocol achieves forward secrecy and post-compromise security. We evaluate the performance of a prototype implementation, and demonstrate that our protocol has practical efficiency.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Nov 12, 2021•28 citations

A Concrete Treatment of Efficient Continuous Group Key Agreement via Multi-Recipient PKEs

Keitaro Hashimoto, Shuichi Katsumata, Eamonn W. Postlethwaite +2 more

Continuous group key agreements (CGKAs) are a class of protocols that can provide strong security guarantees to secure group messaging protocols such as Signal and MLS. Protection against device compromise is provided by commit messages: at a regular rate, each group member may refresh their key material by uploading a commit message, which is then downloaded and processed by all the other members. In practice, propagating commit messages dominates the bandwidth consumption of existing CGKAs.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Nov 12, 2021•28 citations

Keep the Dirt: Tainted TreeKEM, Adaptively and Actively Secure Continuous Group Key Agreement

Karen Klein, Guillermo Pascual-Perez, Michael Walter +7 more

While messaging systems with strong security guarantees are widely used in practice, designing a protocol that scales efficiently to large groups and enjoys similar security guarantees remains largely open. The two existing proposals to date are ART (Cohn-Gordon et al., CCS18) and TreeKEM (IETF, The Messaging Layer Security Protocol, draft). TreeKEM is the currently considered candidate by the IETF MLS working group, but dynamic group operations (i.e. adding and removing users) can cause efficiency issues. In this paper we formalize and analyze a variant of TreeKEM which we term Tainted TreeKEM (TTKEM for short). The basic idea underlying TTKEM was suggested by Millican (MLS mailing list, February 2018). This version is more efficient than TreeKEM for some natural distributions of group operations, we quantify this through simulations.Our second contribution is two security proofs for TTKEM which establish post compromise and forward secrecy even against adaptive attackers. The security loss (to the underlying PKE) in the Random Oracle Model is a polynomial factor, and a quasipolynomial one in the Standard Model. Our proofs can be adapted to TreeKEM as well. Before our work no security proof for any TreeKEM-like protocol establishing tight security against an adversary who can adaptively choose the sequence of operations was known. We also are the first to prove (or even formalize) active security where the server can arbitrarily deviate from the protocol specification. Proving fully active security – where also the users can arbitrarily deviate – remains open.

IEEE Symposium on Security and Privacy (S&P)•May 1, 2021•30 citations
Secure Group Messagings are cryptographic protocols that allow safe group conversation within potentially large user groups. They are based on a dedicated type of group key exchange mechanism named Continuous Group Key Agreement (CGKA), which generates a continuously evolving group key in a safe and efficient way. Messaging Layer Security (MLS) is an IETF-standardized secure group messaging protocol which uses a protocol called TreeKEM as its CGKA.We study in this thesis the security and the efficiency of the CGKAs used within secure group messagings. Firstly, we propose a variant of TreeKEM (called Quarantined-TreeKEM) that solves a security issue related to inactive users, whose behavior prevents fundamental security properties to be fulfilled. Moreover, we improve the efficiency of TreeKEM, especially regarding its communication cost, by considering the best way to manage the tree graph used by that CGKA. Finally, we show that in the particular – yet common – use case where only a subset of users is granted the administration rights, we can design a new CGKA whose performances outperform those of regular decentralized CGKAs such as TreeKEM.This thesis thus aims to improve the state-of-the-art in secure group messaging protocols, in a context where strong security and energy sobriety are necessary features.
The recently standardized secure group messaging protocol Messaging Layer Security (MLS) is designed to ensure asynchronous communications within large groups, with an almost-optimal communication cost and the same security level as point-to-point secure messaging protocols such as Signal. In particular, the core sub-protocol of MLS, a Continuous Group Key Agreement (CGKA) called TreeKEM, must generate a common group key that respects the fundamental security properties of post-compromise security and forward secrecy which mitigate the effects of user corruption over time
Secure messaging (SM) protocols allow users to communicate securely over an untrusted infrastructure. Alwen et al. formally defined the key agreement protocol used in secure group messaging (SGM) as continuous group key agreement (CGKA) at CRYPTO 2020. In their CGKA protocol, all of the group members have the same rights to execute algorithms, and a trusted third party is needed. On the other hand, some applications such as a broadcasting service may have an administrator in the group. When the administrator as the group manager (GM) is distinguished from other group members, i.e., in a one-to-many setting, it would be better for the GM and the other group members to have different authorities. We propose a new CGKA protocol, called CGKA with flexible authorization (CGKA-FA) by incorporating a ratcheting digital signature scheme (Cremers et al. at USENIX Security 2021) into the existing CGKA protocol and demonstrate that such a simple modification allows us to provide flexible authorization. Our proposed protocol does not need an external public key infrastructure (PKI) functionality as a trusted third party. So no third party outside the group handles confidential information of users and thus no one except group members can read messages regardless of key updates. In our CGKA-FA protocol, it is possible to set privileges of users in a group flexibly, which is highly compatible with the field of broadcasting.
Secure messaging (SM) protocols allow users to communicate se-curely over an untrusted infrastructure. Alwen et al. formally de-fined the key agreement protocol used in secure group messaging (SGM) as continuous group key agreement (CGKA) at CRYPTO 2020. In their CGKA protocol, all of the group members have the same rights and a trusted third party is needed. On the other hand, some SGM applications may have a user in the group who has the role of an administrator. When the administrator as the group manager (GM) is distinguished from other group members, i.e., in a one-to-many setting, it would be better for the GM and the other group members to have different authorities. We achieve this flex-ible authorization by incorporating a ratcheting digital signature scheme (Cremers et al. at USENIX Security 2021) into the existing CGKA protocol and demonstrate that such a simple modification allows us to provide flexible authorization. In Alwen et al.'s CGKA protocol, an external public key infrastructure (PKI) functionality as a trusted third party manages the confidential information of users, and the PKI can read all messages until all users update their own keys. In contrast, the GM in our protocol has the same role as the PKI functionality in the group, so no third party outside the group handles confidential information of users and thus no one except group members can read messages regardless of key updates. Our proposed protocol is useful in the creation of new applications such as broadcasting services.
Secure group messaging protocols, providing end-to-end encryption for group communication, need to handle mobile devices frequently being offline, group members being added or removed, and the possibility of device compromises during long-lived chat sessions. Existing work targets a centralized network model in which all messages are routed through a single server, which is trusted to provide a consistent total order on updates to the group state. In this paper we adapt secure group messaging for decentralized networks that have no central authority. Servers may still optionally be used, but they are trusted less. We define decentralized continuous group key agreement (DCGKA), a new cryptographic primitive encompassing the core of a decentralized secure group messaging protocol; we give a practical construction of a DCGKA protocol and prove its security; and we describe how to construct a full messaging protocol from DCGKA. In the face of device compromise our protocol achieves forward secrecy and post-compromise security. We evaluate the performance of a prototype implementation, and demonstrate that our protocol has practical efficiency.
While messaging systems with strong security guarantees are widely used in practice, designing a protocol that scales efficiently to large groups and enjoys similar security guarantees remains largely open. The two existing proposals to date are ART (Cohn-Gordon et al., CCS18) and TreeKEM (IETF, The Messaging Layer Security Protocol, draft). TreeKEM is the currently considered candidate by the IETF MLS working group, but dynamic group operations (i.e. adding and removing users) can cause efficiency issues. In this paper we formalize and analyze a variant of TreeKEM which we term Tainted TreeKEM (TTKEM for short). The basic idea underlying TTKEM was suggested by Millican (MLS mailing list, February 2018). This version is more efficient than TreeKEM for some natural distributions of group operations, we quantify this through simulations.Our second contribution is two security proofs for TTKEM which establish post compromise and forward secrecy even against adaptive attackers. The security loss (to the underlying PKE) in the Random Oracle Model is a polynomial factor, and a quasipolynomial one in the Standard Model. Our proofs can be adapted to TreeKEM as well. Before our work no security proof for any TreeKEM-like protocol establishing tight security against an adversary who can adaptively choose the sequence of operations was known. We also are the first to prove (or even formalize) active security where the server can arbitrarily deviate from the protocol specification. Proving fully active security – where also the users can arbitrarily deviate – remains open.