Continuous Group Key Agreement
Definition
Our security definition for CGKA protocols requires that (i) users obtain the same update secrets (correctness), (ii) update secrets look random to an attacker observing the protocol messages, (iii) past update secrets remain random even if the state of a party is compromised by the attacker (FS), and (iv) parties can recover from state compromise (PCS). All of these properties are captured by a single, fairly intuitive security game.
We argue that the formal security properties of CGKA are phrased in such a way that it is a suitable building block for full SGM protocols. In particular, CGKA is inspired by the modularization of Alwen et al. [2], who constructed a secure two-party messaging protocol (based on the double-ratchet paradigm) by combining three primitives: continuous key agreement (CKA), forward secure authenticated encryption with associated data (FS-AEAD), and a so-called PRF-PRNG, which is a two-input hash function that is a pseudo-random function (resp. generator) with respect to its first (resp. second) input. CGKA is therefore to be seen as the multi-user analogue of CKA and is tailored to be used in conjunction with a PRF-PRNG and the multi-user version of FS-AEAD. Specifically, the update secret is run through the PRF-PRNG in order to obtain new keys for the multi-user FS-AEAD. Due to the already quite high complexity of CGKA itself, this work focuses exclusively on CGKA and sketches how it can be used in a higher-level protocol to obtain a full SGM protocol.
Security Analysis and Improvements for the IETF MLS Standard for Group Messaging p.251
A continuous group key agreement (CGKA) protocol allows a long-lived dynamic group to agree on a continuous stream of fresh secret group keys. In CGKA new parties may join and existing members may leave the group at any point mid-session. In contrast to standard (dynamic) GKA, the CGKA protocols are asynchronous in that they make no assumptions about if, when, or for how long members are online. Moreover, unlike, say, broadcast encryption, the protocol may not rely on a (trusted) group manager or any other designated party. Due to a session’s potentially very long life-time (e.g., years), CGKA protocols must ensure a property called post-compromise forward security (PCFS). PCFS strengthens the two standard notions of forward security (FS) (the keys output must remain secure even if some party’s state is compromised in the future) and post-compromise security (PCS) (parties recover from state compromise after exchanging a few messages and the keys become secure again) in that it requires them to hold simultaneously.
History
The first CGKA protocol was introduced by Cohn-Gordon et al. in [15] although CGKA as a (term and) generic stand-alone primitive was only later introduced by Alwen et al. in [4]. To motivate the new primitive [4] puts forth the intuition that CGKA abstracts the cryptographic core of an “MLS-like” approach to SGM protocol design in much the same way that CKA (the 2-party analogue of CGKA) abstracts the asymmetric core of a double-ratchet based 2-party secure messaging protocol [1]. Indeed, MLS’s computational and communication complexities, support for dynamic groups, it’s asynchronous nature, trust assumptions and it’s basic security guarantees are naturally inherited from the underlying TreeKEM CGKA sub-protocol. Finally, we believe that the fundamental nature of key agreement and the increasing focus on highly distributed practical cryptographic protocols surely allows for further interesting applications of CGKA beyond SGM.
[1]: The Double Ratchet - Security Notions, Proofs, and Modularization for the Signal Protocol
[4]: Security Analysis and Improvements for the IETF MLS Standard for Group Messaging
[15]: On Ends-to-Ends Encryption - Asynchronous Group Messaging with Strong Security Guarantees