---
_id: '11476'
abstract:
- lang: eng
  text: "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 efficiently scale to large groups. A
    major bottleneck are the frequent key rotations users need to perform to achieve
    post compromise forward security.\r\n\r\nIn 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.\r\n\r\nIn larger groups, having users sequentially rotate their keys requires
    too much bandwidth (or takes too long), so variants allowing any T≤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 Ω(T) communication for each user [Bienstock et al., TCC’20].\r\n\r\nIn
    this paper we propose CoCoA; a new 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 Ω(log2(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.\r\n\r\nThe
    key insight of our 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.\r\n\r\nTo 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."
acknowledgement: We thank Marta Mularczyk and Yiannis Tselekounis for their very helpful
  feedback on an earlier draft of this paper.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Joël
  full_name: Alwen, Joël
  last_name: Alwen
- first_name: Benedikt
  full_name: Auerbach, Benedikt
  id: D33D2B18-E445-11E9-ABB7-15F4E5697425
  last_name: Auerbach
  orcid: 0000-0002-7553-6606
- first_name: Miguel
  full_name: Cueto Noval, Miguel
  id: ffc563a3-f6e0-11ea-865d-e3cce03d17cc
  last_name: Cueto Noval
  orcid: 0000-0002-2505-4246
- first_name: Karen
  full_name: Klein, Karen
  id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
  last_name: Klein
- first_name: Guillermo
  full_name: Pascual Perez, Guillermo
  id: 2D7ABD02-F248-11E8-B48F-1D18A9856A87
  last_name: Pascual Perez
  orcid: 0000-0001-8630-415X
- first_name: Krzysztof Z
  full_name: Pietrzak, Krzysztof Z
  id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
  last_name: Pietrzak
  orcid: 0000-0002-9139-1654
- first_name: Michael
  full_name: Walter, Michael
  last_name: Walter
citation:
  ama: 'Alwen J, Auerbach B, Cueto Noval M, et al. CoCoA: Concurrent continuous group
    key agreement. In: <i>Advances in Cryptology – EUROCRYPT 2022</i>. Vol 13276.
    Cham: Springer Nature; 2022:815–844. doi:<a href="https://doi.org/10.1007/978-3-031-07085-3_28">10.1007/978-3-031-07085-3_28</a>'
  apa: 'Alwen, J., Auerbach, B., Cueto Noval, M., Klein, K., Pascual Perez, G., Pietrzak,
    K. Z., &#38; Walter, M. (2022). CoCoA: Concurrent continuous group key agreement.
    In <i>Advances in Cryptology – EUROCRYPT 2022</i> (Vol. 13276, pp. 815–844). Cham:
    Springer Nature. <a href="https://doi.org/10.1007/978-3-031-07085-3_28">https://doi.org/10.1007/978-3-031-07085-3_28</a>'
  chicago: 'Alwen, Joël, Benedikt Auerbach, Miguel Cueto Noval, Karen Klein, Guillermo
    Pascual Perez, Krzysztof Z Pietrzak, and Michael Walter. “CoCoA: Concurrent Continuous
    Group Key Agreement.” In <i>Advances in Cryptology – EUROCRYPT 2022</i>, 13276:815–844.
    Cham: Springer Nature, 2022. <a href="https://doi.org/10.1007/978-3-031-07085-3_28">https://doi.org/10.1007/978-3-031-07085-3_28</a>.'
  ieee: 'J. Alwen <i>et al.</i>, “CoCoA: Concurrent continuous group key agreement,”
    in <i>Advances in Cryptology – EUROCRYPT 2022</i>, Trondheim, Norway, 2022, vol.
    13276, pp. 815–844.'
  ista: 'Alwen J, Auerbach B, Cueto Noval M, Klein K, Pascual Perez G, Pietrzak KZ,
    Walter M. 2022. CoCoA: Concurrent continuous group key agreement. Advances in
    Cryptology – EUROCRYPT 2022. EUROCRYPT: Theory and Applications of Cryptology
    and Information Security, LNCS, vol. 13276, 815–844.'
  mla: 'Alwen, Joël, et al. “CoCoA: Concurrent Continuous Group Key Agreement.” <i>Advances
    in Cryptology – EUROCRYPT 2022</i>, vol. 13276, Springer Nature, 2022, pp. 815–844,
    doi:<a href="https://doi.org/10.1007/978-3-031-07085-3_28">10.1007/978-3-031-07085-3_28</a>.'
  short: J. Alwen, B. Auerbach, M. Cueto Noval, K. Klein, G. Pascual Perez, K.Z. Pietrzak,
    M. Walter, in:, Advances in Cryptology – EUROCRYPT 2022, Springer Nature, Cham,
    2022, pp. 815–844.
conference:
  end_date: 2022-06-03
  location: Trondheim, Norway
  name: 'EUROCRYPT: Theory and Applications of Cryptology and Information Security'
  start_date: 2022-05-30
corr_author: '1'
date_created: 2022-06-30T16:48:00Z
date_published: 2022-05-25T00:00:00Z
date_updated: 2026-04-07T13:01:26Z
day: '25'
department:
- _id: GradSch
- _id: KrPi
doi: 10.1007/978-3-031-07085-3_28
ec_funded: 1
external_id:
  isi:
  - '000832305300028'
intvolume: '     13276'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprint.iacr.org/2022/251
month: '05'
oa: 1
oa_version: Preprint
page: 815–844
place: Cham
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '682815'
  name: Teaching Old Crypto New Tricks
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '665385'
  name: International IST Doctoral Program
publication: Advances in Cryptology – EUROCRYPT 2022
publication_identifier:
  eisbn:
  - '9783031070853'
  eissn:
  - 1611-3349
  isbn:
  - '9783031070846'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
  record:
  - id: '18088'
    relation: dissertation_contains
    status: public
scopus_import: '1'
status: public
title: 'CoCoA: Concurrent continuous group key agreement'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13276
year: '2022'
...