Paper 2022/251

CoCoA: Concurrent Continuous Group Key Agreement

Joël Alwen, AWS Wickr
Benedikt Auerbach, Institute of science and Technology Austria ISTA
Miguel Cueto Noval, Institute of science and Technology Austria ISTA
Karen Klein, ETH Zurich
Guillermo Pascual-Perez, Institute of science and Technology Austria ISTA
Krzysztof Pietrzak, Institute of science and Technology Austria ISTA
Michael Walter, Zama
Abstract

Messaging platforms like Signal are widely deployed and provide strong security in an asynchronous setting. It is a challenging problem to construct a protocol with similar security guarantees that can \emph{efficiently} scale to large groups. A major bottleneck are the frequent key rotations users need to perform to achieve post compromise forward security. In current proposals -- most notably in TreeKEM (which is part of the IETF's Messaging Layer Security (MLS) protocol draft) -- for users in a group of size $n$ to rotate their keys, they must each craft a message of size $\log(n)$ to be broadcast to the group using an (untrusted) delivery server. In larger groups, having users sequentially rotate their keys requires too much bandwidth (or takes too long), so variants allowing any $T \leq n$ users to simultaneously rotate their keys in just $2$ communication rounds have been suggested (e.g. "Propose and Commit" by MLS). Unfortunately, $2$-round concurrent updates are either damaging or expensive (or both); i.e. they either result in future operations being more costly (e.g. via "blanking'' or "tainting'') or are costly themselves requiring $\Omega(T)$ communication for each user [Bienstock et al., TCC'20]. In this paper we propose CoCoA; a scheme that allows for $T$ concurrent updates that are neither damaging nor costly. That is, they add no cost to future operations yet they only require $\Omega(\log^2(n))$ communication per user. To circumvent the [Bienstock et al.] lower bound, CoCoA increases the number of rounds needed to complete all updates from $2$ up to (at most) $\log(n)$; though typically fewer rounds are needed. The key insight of the protocol is the following: in the (non-concurrent version of) TreeKEM, a delivery server which gets $T$ concurrent update requests will approve one and reject the remaining $T-1$. In contrast, our server attempts to apply all of them. If more than one user requests to rotate the same key during a round, the server arbitrarily picks a winner. Surprisingly, we prove that regardless of how the server chooses the winners, all previously compromised users will recover after at most $\log(n)$ such update rounds. To keep the communication complexity low, CoCoA is a server-aided CGKA. That is, the delivery server no longer blindly forwards packets, but instead actively computes individualized packets tailored to each user. As the server is untrusted, this change requires us to develop new mechanisms ensuring robustness of the protocol.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in EUROCRYPT 2022
DOI
10.1007/978-3-031-07085-3_28
Keywords
secure group messagingCGKAMLSconcurrent updates
Contact author(s)
alwenjo @ amazon com
bauerbac @ ista ac at
mcuetono @ ista ac at
karen klein @ inf ethz ch
gpasper @ protonmail com
pietrzak @ ista ac at
michael walter @ zama ai
History
2023-07-20: revised
2022-03-02: received
See all versions
Short URL
https://ia.cr/2022/251
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/251,
      author = {Joël Alwen and Benedikt Auerbach and Miguel Cueto Noval and Karen Klein and Guillermo Pascual-Perez and Krzysztof Pietrzak and Michael Walter},
      title = {CoCoA: Concurrent Continuous Group Key Agreement},
      howpublished = {Cryptology ePrint Archive, Paper 2022/251},
      year = {2022},
      doi = {10.1007/978-3-031-07085-3_28},
      note = {\url{https://eprint.iacr.org/2022/251}},
      url = {https://eprint.iacr.org/2022/251}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.