Paper 2022/559

DeCAF: Decentralizable Continuous Group Key Agreement with Fast Healing

Joël Alwen, Benedikt Auerbach, Miguel Cueto Noval, Karen Klein, Guillermo Pascual-Perez, and Krzysztof Pietrzak


Continuous group key agreement (CGKA) allows a group of users to maintain a continuously updated shared key in an asynchronous setting where parties only come online sporadically and their messages are relayed by an untrusted server. CGKA captures the basic primitive underlying group messaging schemes. Current solutions including TreeKEM (``Message Layer Security'' (MLS) IETF draft) cannot handle concurrent requests while retaining low communication complexity. The exception being CoCoA, which is concurrent while having extremely low communication complexity (in groups of size $n$ and for $m$ concurrent updates the communication per user is $\log(n)$, i.e., independent of $m$). The main downside of CoCoA is that in groups of size $n$, users might have to do up to $\log(n)$ update requests to the server to ensure their (potentially corrupted) key material has been refreshed. We present a new ``fast healing'' concurrent CGKA protocol, named DeCAF, where users will heal after at most $\log(t)$ requests, with $t$ being the number of corrupted users. Our new protocol is particularly interesting to realize decentralized group messaging, where protocol messages (add/remove/update) are being posted on a blockchain rather than sent to a server. In this setting, concurrency is crucial once requests are more frequent than blocks. Our new protocol significantly outperforms (the only alternative with sub-linear communication and PCS) CoCoA in this setting: it heals much faster ($\log(t)$ vs. $\log(n)$ rounds). The communication per round and user is $m\cdot\log(n)$, but in this setting -- where there is no server who can craft specific messages to users depending on their position in the tree -- CoCoA requires the same communication.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
group messagingCGKAMLS
Contact author(s)
gpascual @ ist ac at
2022-05-12: revised
2022-05-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Joël Alwen and Benedikt Auerbach and Miguel Cueto Noval and Karen Klein and Guillermo Pascual-Perez and Krzysztof Pietrzak},
      title = {DeCAF: Decentralizable Continuous Group Key Agreement with Fast Healing},
      howpublished = {Cryptology ePrint Archive, Paper 2022/559},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.