Cryptology ePrint Archive: Report 2022/559

DeCAF: Decentralizable Continuous Group Key Agreement with Fast Healing

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

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

Category / Keywords: cryptographic protocols / group messaging, CGKA, MLS

Date: received 8 May 2022, last revised 12 May 2022

Contact author: gpascual at ist ac at

Available format(s): PDF | BibTeX Citation

Version: 20220512:101259 (All versions of this report)

Short URL: ia.cr/2022/559


[ Cryptology ePrint archive ]