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

ACM SIGSAC Conference on Computer and Communications Security (CCS)

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

Céline Chevalier, Guirec Lebrun, Ange Martinelli, Abdul Rahman Taleb

Published Dec 2, 2024• 3 citations
Publisher

Abstract

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

DOI
10.1145/3658644.3690265

Related papers

Security and Efficiency of Secure Group Messaging Protocols

Guirec Lebrun

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.

•Dec 1, 2025•0 citations

Quadtree-Based Optimized MLS Protocol with Inactive-User Isolation

Yiyang Guo, Kerun Wang, Lifan Wang

For long-term asynchronous group instant messaging, the Messaging Layer Security (MLS) protocol is required to provide both forward secrecy and post-compromise security over an untrusted server. However, when post-quantum cryptographic suites are adopted, the TreeKEM core based on a perfect binary tree cannot achieve optimal communication and computation costs, and only supports a simple eviction strategy for long-term offline inactive users, which introduces both performance and security concerns. To address these challenges, this paper proposes an optimized MLS scheme based on a quadtree structure with support for inactive-user isolation. By restructuring the TreeKEM tree and introducing a threshold secret-sharing–based isolation mechanism, the scheme jointly reduces communication and computation overhead while preserving the original security guarantees and enhancing the overall group security. Our experimental results further demonstrate that the bottom-expanded quadtree TreeKEM achieves lower overall cost than its binary and ternary counterparts in post-quantum settings, and can significantly improve the performance of MLS while strengthening group security.

International Symposium on Computer Engineering and Intelligent Communications (ISCEIC)•Nov 24, 2025•0 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

Revisiting Post-Compromise Security Guarantees in Group Messaging.

Cas J. F. Cremers, Britta Hale, Konrad Kohbrok

Modern secure messaging protocols can offer strong security guarantees such as Post-Compromise Security (PCS), which enables participants to heal after compromise. The core PCS mechanism in protocols like Signal is designed for pairwise communication, making it inefficient for large groups, while recently proposed designs for secure group messaging, ART, IETF's MLS Draft-11/TreeKEM, use group keys derived from tree structures to efficiently provide PCS to large groups. Until now, research on PCS designs only considered healing behaviour within a single group. In this work we provide the first analysis of the healing behaviour when a user participates in multiple groups. Our analysis reveals that the currently proposed protocols based on group keys, such as ART and TreeKEM/MLS Draft-11, provide significantly weaker PCS guarantees than group protocols based on pairwise PCS channels. In fact, we show that if new users can be created dynamically, ART, TreeKEM, and MLS Draft-11 never fully heal authentication. We map the design space of healing mechanisms, analyzing security and overhead of possible solutions. This leads us to a promising solution based on (i) global updates that affect all current and future groups, and (ii) post-compromise secure signatures. Our solution allows group messaging protocols such ART and MLS to achieve substantially stronger PCS guarantees. We provide a security definition for post-compromise secure signatures and an instantiation.

•May 10, 2019•4 citations

Server-Aided Continuous Group Key Agreement

Joël Alwen, Dominik Hartmann, Eike Kiltz +1 more

Continuous Group Key Agreement (CGKA) -- or Group Ratcheting -- lies at the heart of a new generation of scalable End-to-End secure (E2E) cryptographic multi-party applications. One of the most important (and first deployed) CGKAs is ITK which underpins the IETF's upcoming Messaging Layer Security E2E secure group messaging standard. To scale beyond the group sizes possible with earlier E2E protocols, a central focus of CGKA protocol design is to minimize bandwidth requirements (i.e. communication complexity).

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Nov 7, 2022•26 citations
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 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.
For long-term asynchronous group instant messaging, the Messaging Layer Security (MLS) protocol is required to provide both forward secrecy and post-compromise security over an untrusted server. However, when post-quantum cryptographic suites are adopted, the TreeKEM core based on a perfect binary tree cannot achieve optimal communication and computation costs, and only supports a simple eviction strategy for long-term offline inactive users, which introduces both performance and security concerns. To address these challenges, this paper proposes an optimized MLS scheme based on a quadtree structure with support for inactive-user isolation. By restructuring the TreeKEM tree and introducing a threshold secret-sharing–based isolation mechanism, the scheme jointly reduces communication and computation overhead while preserving the original security guarantees and enhancing the overall group security. Our experimental results further demonstrate that the bottom-expanded quadtree TreeKEM achieves lower overall cost than its binary and ternary counterparts in post-quantum settings, and can significantly improve the performance of MLS while strengthening group security.
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.
Modern secure messaging protocols can offer strong security guarantees such as Post-Compromise Security (PCS), which enables participants to heal after compromise. The core PCS mechanism in protocols like Signal is designed for pairwise communication, making it inefficient for large groups, while recently proposed designs for secure group messaging, ART, IETF's MLS Draft-11/TreeKEM, use group keys derived from tree structures to efficiently provide PCS to large groups. Until now, research on PCS designs only considered healing behaviour within a single group. In this work we provide the first analysis of the healing behaviour when a user participates in multiple groups. Our analysis reveals that the currently proposed protocols based on group keys, such as ART and TreeKEM/MLS Draft-11, provide significantly weaker PCS guarantees than group protocols based on pairwise PCS channels. In fact, we show that if new users can be created dynamically, ART, TreeKEM, and MLS Draft-11 never fully heal authentication. We map the design space of healing mechanisms, analyzing security and overhead of possible solutions. This leads us to a promising solution based on (i) global updates that affect all current and future groups, and (ii) post-compromise secure signatures. Our solution allows group messaging protocols such ART and MLS to achieve substantially stronger PCS guarantees. We provide a security definition for post-compromise secure signatures and an instantiation.
Continuous Group Key Agreement (CGKA) -- or Group Ratcheting -- lies at the heart of a new generation of scalable End-to-End secure (E2E) cryptographic multi-party applications. One of the most important (and first deployed) CGKAs is ITK which underpins the IETF's upcoming Messaging Layer Security E2E secure group messaging standard. To scale beyond the group sizes possible with earlier E2E protocols, a central focus of CGKA protocol design is to minimize bandwidth requirements (i.e. communication complexity).