International Symposium on Computer Engineering and Intelligent Communications (ISCEIC)

Quadtree-Based Optimized MLS Protocol with Inactive-User Isolation

Yiyang Guo, Kerun Wang, Lifan Wang

Published Nov 24, 2025• 0 citations

Abstract

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.

DOI: 10.1109/isceic67854.2025.11405672

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, 20243 citations

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, 20250 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, 20194 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, 202130 citations

On Ends-to-Ends Encryption: Asynchronous Group Messaging with Strong Security Guarantees

Katriel Cohn-Gordon, Cas J. F. Cremers, Luke Garratt +2 more

In the past few years secure messaging has become mainstream, with over a billion active users of end-to-end encryption protocols such as Signal. The Signal Protocol provides a strong property called post-compromise security to its users. However, it turns out that many of its implementations provide, without notification, a weaker property for group messaging: an adversary who compromises a single group member can read and inject messages indefinitely. We show for the first time that post-compromise security can be achieved in realistic, asynchronous group messaging systems. We present a design called Asynchronous Ratcheting Trees (ART), which uses tree-based Diffie-Hellman key exchange to allow a group of users to derive a shared symmetric key even if no two are ever online at the same time. ART scales to groups containing thousands of members, while still providing provable security guarantees. It has seen significant interest from industry, and forms the basis for two draft IETF RFCs and a chartered working group. Our results show that strong security guarantees for group messaging are practically achievable in a modern setting.

Jul 1, 201818 citations

Development of an Instant Messaging Application Based on MLS using QRNG-Generated Keys

Manuel Lagos Rodríguez, Hilda Romero Velo, Álvaro Leitao +2 more

Nowadays, instant messaging applications have become the main channel of communication between people. In response to demands of privacy by users, some applications have begun to incorporate end-to-end encryption to protect conversations. The Messaging Layer Security (MLS) is a recent protocol that offers end-to-end encryption designed for groups, providing both efficiency and security. In this work we develop a messaging application that uses MLS as the basis for secure communications between users. The application will use a peer-to-peer network to prevent messages from passing through servers that could store them and try to decrypt them. Furthermore, the cryptographic keys used will be generated by a Quantum Random Number Generator and accessed through an Entropy-as-a-Service platform.

May 14, 20260 citations