---
res:
  bibo_abstract:
  - "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.@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Benedikt
      foaf_name: Auerbach, Benedikt
      foaf_surname: Auerbach
      foaf_workInfoHomepage: http://www.librecat.org/personId=D33D2B18-E445-11E9-ABB7-15F4E5697425
    orcid: 0000-0002-7553-6606
  - foaf_Person:
      foaf_givenName: Miguel
      foaf_name: Cueto Noval, Miguel
      foaf_surname: Cueto Noval
      foaf_workInfoHomepage: http://www.librecat.org/personId=ffc563a3-f6e0-11ea-865d-e3cce03d17cc
    orcid: 0000-0002-2505-4246
  - foaf_Person:
      foaf_givenName: Guillermo
      foaf_name: Pascual Perez, Guillermo
      foaf_surname: Pascual Perez
      foaf_workInfoHomepage: http://www.librecat.org/personId=2D7ABD02-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0001-8630-415X
  - foaf_Person:
      foaf_givenName: Krzysztof Z
      foaf_name: Pietrzak, Krzysztof Z
      foaf_surname: Pietrzak
      foaf_workInfoHomepage: http://www.librecat.org/personId=3E04A7AA-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0002-9139-1654
  bibo_doi: 10.1007/978-3-031-48621-0_10
  bibo_volume: 14371
  dct_date: 2023^xs_gYear
  dct_identifier:
  - UT:001160724400010
  dct_isPartOf:
  - http://id.crossref.org/issn/0302-9743
  - http://id.crossref.org/issn/1611-3349
  - http://id.crossref.org/issn/9783031486203
  dct_language: eng
  dct_publisher: Springer Nature@
  dct_title: On the cost of post-compromise security in concurrent Continuous Group-Key
    Agreement@
...