Multicast Key Agreement, Revisited

Alexander Bienstock, Yevgeniy Dodis, Yi Tang

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Multicast Key Agreement (MKA) is a long-overlooked natural primitive of large practical interest. In traditional MKA, an omniscient group manager privately distributes secrets over an untrusted network to a dynamically-changing set of group members. The group members are thus able to derive shared group secrets across time, with the main security requirement being that only current group members can derive the current group secret. There indeed exist very efficient MKA schemes in the literature that utilize symmetric-key cryptography. However, they lack formal security analyses, efficiency analyses regarding dynamically changing groups, and more modern, robust security guarantees regarding user state leakages: forward secrecy (FS) and post-compromise security (PCS). The former ensures that group secrets prior to state leakage remain secure, while the latter ensures that after such leakages, users can quickly recover security of group secrets via normal protocol operations. More modern Secure Group Messaging (SGM) protocols allow a group of users to asynchronously and securely communicate with each other, as well as add and remove each other from the group. SGM has received significant attention recently, including in an effort by the IETF Messaging Layer Security (MLS) working group to standardize an eponymous protocol. However, the group key agreement primitive at the core of SGM protocols, Continuous Group Key Agreement (CGKA), achieved by the TreeKEM protocol in MLS, suffers from bad worst-case efficiency and heavily relies on less efficient (than symmetric-key cryptography) public-key cryptography. We thus propose that in the special case of a group membership change policy which allows a single member to perform all group additions and removals, an upgraded version of classical Multicast Key Agreement (MKA) may serve as a more efficient substitute for CGKA in SGM. We therefore present rigorous, stronger MKA security definitions that provide increasing levels of security in the case of both user and group manager state leakage, and that are suitable for modern applications, such as SGM. We then construct a formally secure MKA protocol with strong efficiency guarantees for dynamic groups. Finally, we run experiments which show that the left-balanced binary tree structure used in TreeKEM can be replaced with red-black trees in MKA for better efficiency.

Original languageEnglish (US)
Title of host publicationTopics in Cryptology - CT-RSA 2022 - Cryptographers’ Track at the RSA Conference, 2022, Proceedings
EditorsSteven D. Galbraith
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages25
ISBN (Print)9783030953119
StatePublished - 2022
EventCryptographers Track at the RSA Conference, CT-RSA 2022 - Virtual, Online
Duration: Mar 1 2022Mar 2 2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13161 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceCryptographers Track at the RSA Conference, CT-RSA 2022
CityVirtual, Online

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Multicast Key Agreement, Revisited'. Together they form a unique fingerprint.

Cite this