Paper 2021/1456

Server-Aided Continuous Group Key Agreement

Joël Alwen, AWS-Wickr
Dominik Hartmann, Ruhr University Bochum
Eike Kiltz, Ruhr University Bochum
Marta Mularczyk, AWS-Wickr

Continuous Group Key Agreement (CGKA) -- or Group Ratcheting -- lies at the heart of a new generation of scalable End-to-End secure (E2E) cryptographic multi-party applications. One of the most important (and first deployed) CGKAs is ITK which underpins the IETF's upcoming Messaging Layer Security E2E secure group messaging standard. To scale beyond the group sizes possible with earlier E2E protocols, a central focus of CGKA protocol design is to minimize bandwidth requirements (i.e. communication complexity). In this work, we advance both the theory and design of CGKA culminating in an extremely bandwidth efficient CGKA. To that end, we first generalize the standard CGKA communication model by introducing server-aided CGKA (saCGKA) which generalizes CGKA and more accurately models how most E2E protocols are deployed in the wild. Next, we introduce the SAIK protocol; a modification of ITK, designed for real-world use, that leverages the new capabilities available to an saCGKA to greatly reduce its communication (and computational) complexity in practical concrete terms. Further, we introduce an intuitive, yet precise, security model for saCGKA. It improves upon existing security models for CGKA in several ways. It more directly captures the intuitive security goals of CGKA. Yet, formally it also relaxes certain requirements allowing us to take advantage of the saCGKA communication model. Finally, it is significantly simpler making it more tractable to work with and easier to build intuition for. As a result, the security proof of SAIK is also simpler and more modular. Finally, we provide empirical data comparing the (at times, quite dramatically improved) complexity profile of SAIK to state-of-the art CGKAs. For example, in a newly created group with 10K members, to change the group state (e.g. add/remove parties) ITK requires each group member download 1.38MB. However, with SAIK, members download no more than 2.7KB.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. ACM CCS 2022
group messaging CGKA end-to-end encryption
Contact author(s)
alwenjo @ amazon com
dominik hartmann @ rub de
eike kiltz @ rub de
mulmarta @ amazon com
2022-09-08: revised
2021-11-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Joël Alwen and Dominik Hartmann and Eike Kiltz and Marta Mularczyk},
      title = {Server-Aided Continuous Group Key Agreement},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1456},
      year = {2021},
      doi = {10.1145/3548606.3560632},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.