Paper 2019/477

The Complexities of Healing in Secure Group Messaging: Why Cross-Group Effects Matter

Cas Cremers, Britta Hale, and 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.

Note: Significant update and the longer version of the extended abstract appearing at USENIX 2021.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
post-compromise securityforward secrecygroup messaging protocolsmessage-layer security
Contact author(s)
cas cremers @ gmail com
britta hale @ nps edu
konrad kohbrok @ aalto fi
2021-07-01: last of 3 revisions
2019-05-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Cas Cremers and Britta Hale and Konrad Kohbrok},
      title = {The Complexities of Healing in Secure Group Messaging: Why Cross-Group Effects Matter},
      howpublished = {Cryptology ePrint Archive, Paper 2019/477},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.