Paper 2022/1237

On the Worst-Case Inefficiency of CGKA

Alexander Bienstock, New York University
Yevgeniy Dodis, New York University
Sanjam Garg, UC Berkeley and NTT Research
Garrison Grogan
Mohammad Hajiabadi, University of Waterloo
Paul Rösler, New York University

Continuous Group Key Agreement (CGKA) is the basis of modern Secure Group Messaging (SGM) protocols. At a high level, a CGKA protocol enables a group of users to continuously compute a shared (evolving) secret while members of the group add new members, remove other existing members, and perform state updates. The state updates allow CGKA to offer desirable security features such as forward secrecy and post-compromise security. CGKA is regarded as a practical primitive in the real-world. Indeed, there is an IETF Messaging Layer Security (MLS) working group devoted to developing a standard for SGM protocols, including the CGKA protocol at their core. Though known CGKA protocols seem to perform relatively well when considering natural sequences of performed group operations, there are no formal guarantees on their efficiency, other than the $O(n)$ bound which can be achieved by trivial protocols, where $n$ is the number of group numbers. In this context, we ask the following questions and provide negative answers. 1. Can we have CGKA protocols that are efficient in the worst case? We start by answering this basic question in the negative. First, we show that a natural primitive that we call Compact Key Exchange (CKE) is at the core of CGKA, and thus tightly captures CGKA's worst-case communication cost. Intuitively, CKE requires that: first, $n$ users non-interactively generate key pairs and broadcast their public keys, then, some other special user securely communicates to these $n$ users a shared key. Next, we show that CKE with communication cost $o(n)$ by the special user cannot be realized in a black-box manner from public-key encryption, thus implying the same for CGKA, where $n$ is the corresponding number of group members. Surprisingly, this impossibility holds even in an offline setting, where parties have access to the sequence of group operations in advance. 2. Can we realize one CGKA protocol that works as well as possible in all cases? Here again, we present negative evidence showing that no such protocol based on black-box use of public-key encryption exists. Specifically, we show two distributions over sequences of group operations such that no CGKA protocol obtains optimal communication costs on both sequences.

Available format(s)
Cryptographic protocols
Publication info
Published by the IACR in TCC 2022
Continuous Group Key Agreement Secure Group Messaging Black-Box separation Lower Bound Post-Compromise Security
Contact author(s)
abienstock @ cs nyu edu
dodis @ cs nyu edu
sanjamg @ berkeley edu
garrisonwgrogan @ gmail com
mdhajiabadi @ uwaterloo ca
paul roesler @ cs nyu edu
2022-09-19: approved
2022-09-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Alexander Bienstock and Yevgeniy Dodis and Sanjam Garg and Garrison Grogan and Mohammad Hajiabadi and Paul Rösler},
      title = {On the Worst-Case Inefficiency of CGKA},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1237},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.