--- _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 - 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 - 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: Advances in Cryptology – EUROCRYPT 2022. Vol 13276. Cham: Springer Nature; 2022:815–844. doi:10.1007/978-3-031-07085-3_28' apa: 'Alwen, J., Auerbach, B., Cueto Noval, M., Klein, K., Pascual Perez, G., Pietrzak, K. Z., & Walter, M. (2022). CoCoA: Concurrent continuous group key agreement. In Advances in Cryptology – EUROCRYPT 2022 (Vol. 13276, pp. 815–844). Cham: Springer Nature. https://doi.org/10.1007/978-3-031-07085-3_28' 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 Advances in Cryptology – EUROCRYPT 2022, 13276:815–844. Cham: Springer Nature, 2022. https://doi.org/10.1007/978-3-031-07085-3_28.' ieee: 'J. Alwen et al., “CoCoA: Concurrent continuous group key agreement,” in Advances in Cryptology – EUROCRYPT 2022, 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: Annual International Conference on the 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.” Advances in Cryptology – EUROCRYPT 2022, vol. 13276, Springer Nature, 2022, pp. 815–844, doi:10.1007/978-3-031-07085-3_28.' 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: Annual International Conference on the Theory and Applications of Cryptology and Information Security' start_date: 2022-05-30 date_created: 2022-06-30T16:48:00Z date_published: 2022-05-25T00:00:00Z date_updated: 2023-08-03T07:25:02Z 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' scopus_import: '1' status: public title: 'CoCoA: Concurrent continuous group key agreement' type: conference user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8 volume: 13276 year: '2022' ...