Home Publications Research Grants Inventions & Patents Awards Additional Research Activities Faculties & Institutions Research Areas

On the Worst-Case Inefficiency of CGKA

Bienstock A, Dodis Y, Garg S, Grogan G, Hajiabadi M, Rösler P (2022)

---

Publication Type: Conference contribution

Publication year: 2022

Journal

Publisher: Springer Science and Business Media Deutschland GmbH

Book Volume: 13748 LNCS

Pages Range: 213-243

Conference Proceedings Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Event location: Chicago, IL

ISBN: 9783031223648

DOI: 10.1007/978-3-031-22365-5_8

Abstract

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.

Authors with CRIS profile

Involved external institutions

How to cite

APA:

Bienstock, A., Dodis, Y., Garg, S., Grogan, G., Hajiabadi, M., & Rösler, P. (2022). On the Worst-Case Inefficiency of CGKA. In Eike Kiltz, Vinod Vaikuntanathan (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 213-243). Chicago, IL, US: Springer Science and Business Media Deutschland GmbH.

MLA:

Bienstock, Alexander, et al. "On the Worst-Case Inefficiency of CGKA." Proceedings of the 20th Theory of Cryptography Conference, TCC 2022, Chicago, IL Ed. Eike Kiltz, Vinod Vaikuntanathan, Springer Science and Business Media Deutschland GmbH, 2022. 213-243.

BibTeX: Download