On the Worst-Case Inefficiency of CGKA

Alexander Bienstock, Yevgeniy Dodis, Sanjam Garg, Garrison Grogan, Mohammad Hajiabadi, Paul Rösler

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

    2 Scopus citations


    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.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.

    Original languageEnglish (US)
    Title of host publicationTheory of Cryptography - 20th International Conference, TCC 2022, Proceedings
    EditorsEike Kiltz, Vinod Vaikuntanathan
    PublisherSpringer Science and Business Media Deutschland GmbH
    Number of pages31
    ISBN (Print)9783031223648
    StatePublished - 2022
    Event20th Theory of Cryptography Conference, TCC 2022 - Chicago, United States
    Duration: Nov 7 2022Nov 10 2022

    Publication series

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


    Conference20th Theory of Cryptography Conference, TCC 2022
    Country/TerritoryUnited States

    All Science Journal Classification (ASJC) codes

    • Theoretical Computer Science
    • Computer Science(all)


    Dive into the research topics of 'On the Worst-Case Inefficiency of CGKA'. Together they form a unique fingerprint.

    Cite this