---
_id: '14691'
abstract:
- lang: eng
  text: "Continuous Group-Key Agreement (CGKA) allows a group of users to maintain
    a shared key. It is the fundamental cryptographic primitive underlying group messaging
    schemes and related protocols, most notably TreeKEM, the underlying key agreement
    protocol of the Messaging Layer Security (MLS) protocol, a standard for group
    messaging by the IETF. CKGA works in an asynchronous setting where parties only
    occasionally must come online, and their messages are relayed by an untrusted
    server. The most expensive operation provided by CKGA is that which allows for
    a user to refresh their key material in order to achieve forward secrecy (old
    messages are secure when a user is compromised) and post-compromise security (users
    can heal from compromise). One caveat of early CGKA protocols is that these update
    operations had to be performed sequentially, with any user wanting to update their
    key material having had to receive and process all previous updates. Late versions
    of TreeKEM do allow for concurrent updates at the cost of a communication overhead
    per update message that is linear in the number of updating parties. This was
    shown to be indeed necessary when achieving PCS in just two rounds of communication
    by [Bienstock et al. TCC’20].\r\nThe recently proposed protocol CoCoA [Alwen et
    al. Eurocrypt’22], however, shows that this overhead can be reduced if PCS requirements
    are relaxed, and only a logarithmic number of rounds is required. The natural
    question, thus, is whether CoCoA is optimal in this setting.\r\nIn this work we
    answer this question, providing a lower bound on the cost (concretely, the amount
    of data to be uploaded to the server) for CGKA protocols that heal in an arbitrary
    k number of rounds, that shows that CoCoA is very close to optimal. Additionally,
    we extend CoCoA to heal in an arbitrary number of rounds, and propose a modification
    of it, with a reduced communication cost for certain k.\r\nWe prove our bound
    in a combinatorial setting where the state of the protocol progresses in rounds,
    and the state of the protocol in each round is captured by a set system, each
    set specifying a set of users who share a secret key. We show this combinatorial
    model is equivalent to a symbolic model capturing building blocks including PRFs
    and public-key encryption, related to the one used by Bienstock et al.\r\nOur
    lower bound is of order k•n1+1/(k-1)/log(k), where 2≤k≤log(n) is the number of
    updates per user the protocol requires to heal. This generalizes the n2 bound
    for k=2 from Bienstock et al.. This bound almost matches the k⋅n1+2/(k-1) or k2⋅n1+1/(k-1)
    efficiency we get for the variants of the CoCoA protocol also introduced in this
    paper."
alternative_title:
- LNCS
article_processing_charge: No
author:
- 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: 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
citation:
  ama: 'Auerbach B, Cueto Noval M, Pascual Perez G, Pietrzak KZ. On the cost of post-compromise
    security in concurrent Continuous Group-Key Agreement. In: <i>21st International
    Conference on Theory of Cryptography</i>. Vol 14371. Springer Nature; 2023:271-300.
    doi:<a href="https://doi.org/10.1007/978-3-031-48621-0_10">10.1007/978-3-031-48621-0_10</a>'
  apa: 'Auerbach, B., Cueto Noval, M., Pascual Perez, G., &#38; Pietrzak, K. Z. (2023).
    On the cost of post-compromise security in concurrent Continuous Group-Key Agreement.
    In <i>21st International Conference on Theory of Cryptography</i> (Vol. 14371,
    pp. 271–300). Taipei, Taiwan: Springer Nature. <a href="https://doi.org/10.1007/978-3-031-48621-0_10">https://doi.org/10.1007/978-3-031-48621-0_10</a>'
  chicago: Auerbach, Benedikt, Miguel Cueto Noval, Guillermo Pascual Perez, and Krzysztof
    Z Pietrzak. “On the Cost of Post-Compromise Security in Concurrent Continuous
    Group-Key Agreement.” In <i>21st International Conference on Theory of Cryptography</i>,
    14371:271–300. Springer Nature, 2023. <a href="https://doi.org/10.1007/978-3-031-48621-0_10">https://doi.org/10.1007/978-3-031-48621-0_10</a>.
  ieee: B. Auerbach, M. Cueto Noval, G. Pascual Perez, and K. Z. Pietrzak, “On the cost
    of post-compromise security in concurrent Continuous Group-Key Agreement,” in
    <i>21st International Conference on Theory of Cryptography</i>, Taipei, Taiwan,
    2023, vol. 14371, pp. 271–300.
  ista: 'Auerbach B, Cueto Noval M, Pascual Perez G, Pietrzak KZ. 2023. On the cost
    of post-compromise security in concurrent Continuous Group-Key Agreement. 21st
    International Conference on Theory of Cryptography. TCC: Theory of Cryptography,
    LNCS, vol. 14371, 271–300.'
  mla: Auerbach, Benedikt, et al. “On the Cost of Post-Compromise Security in Concurrent
    Continuous Group-Key Agreement.” <i>21st International Conference on Theory of
    Cryptography</i>, vol. 14371, Springer Nature, 2023, pp. 271–300, doi:<a href="https://doi.org/10.1007/978-3-031-48621-0_10">10.1007/978-3-031-48621-0_10</a>.
  short: B. Auerbach, M. Cueto Noval, G. Pascual Perez, K.Z. Pietrzak, in:, 21st International
    Conference on Theory of Cryptography, Springer Nature, 2023, pp. 271–300.
conference:
  end_date: 2023-12-02
  location: Taipei, Taiwan
  name: 'TCC: Theory of Cryptography'
  start_date: 2023-11-29
corr_author: '1'
date_created: 2023-12-17T23:00:53Z
date_published: 2023-11-27T00:00:00Z
date_updated: 2025-09-09T13:42:16Z
day: '27'
department:
- _id: KrPi
doi: 10.1007/978-3-031-48621-0_10
external_id:
  isi:
  - '001160724400010'
intvolume: '     14371'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprint.iacr.org/2023/1123
month: '11'
oa: 1
oa_version: Preprint
page: 271-300
publication: 21st International Conference on Theory of Cryptography
publication_identifier:
  eissn:
  - 1611-3349
  isbn:
  - '9783031486203'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the cost of post-compromise security in concurrent Continuous Group-Key
  Agreement
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 14371
year: '2023'
...