--- _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 - 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: 21st International Conference on Theory of Cryptography. Vol 14371. Springer Nature; 2023:271-300. doi:10.1007/978-3-031-48621-0_10' apa: 'Auerbach, B., Cueto Noval, M., Pascual Perez, G., & Pietrzak, K. Z. (2023). On the cost of post-compromise security in concurrent Continuous Group-Key Agreement. In 21st International Conference on Theory of Cryptography (Vol. 14371, pp. 271–300). Taipei, Taiwan: Springer Nature. https://doi.org/10.1007/978-3-031-48621-0_10' 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 21st International Conference on Theory of Cryptography, 14371:271–300. Springer Nature, 2023. https://doi.org/10.1007/978-3-031-48621-0_10. 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 21st International Conference on Theory of Cryptography, 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.” 21st International Conference on Theory of Cryptography, vol. 14371, Springer Nature, 2023, pp. 271–300, doi:10.1007/978-3-031-48621-0_10. 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 date_created: 2023-12-17T23:00:53Z date_published: 2023-11-27T00:00:00Z date_updated: 2023-12-18T08:36:51Z day: '27' department: - _id: KrPi doi: 10.1007/978-3-031-48621-0_10 intvolume: ' 14371' 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: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 14371 year: '2023' ... --- _id: '14692' abstract: - lang: eng text: "The generic-group model (GGM) aims to capture algorithms working over groups of prime order that only rely on the group operation, but do not exploit any additional structure given by the concrete implementation of the group. In it, it is possible to prove information-theoretic lower bounds on the hardness of problems like the discrete logarithm (DL) or computational Diffie-Hellman (CDH). Thus, since its introduction, it has served as a valuable tool to assess the concrete security provided by cryptographic schemes based on such problems. A work on the related algebraic-group model (AGM) introduced a method, used by many subsequent works, to adapt GGM lower bounds for one problem to another, by means of conceptually simple reductions.\r\nIn this work, we propose an alternative approach to extend GGM bounds from one problem to another. Following an idea by Yun [EC15], we show that, in the GGM, the security of a large class of problems can be reduced to that of geometric search-problems. By reducing the security of the resulting geometric-search problems to variants of the search-by-hypersurface problem, for which information theoretic lower bounds exist, we give alternative proofs of several results that used the AGM approach.\r\nThe main advantage of our approach is that our reduction from geometric search-problems works, as well, for the GGM with preprocessing (more precisely the bit-fixing GGM introduced by Coretti, Dodis and Guo [Crypto18]). As a consequence, this opens up the possibility of transferring preprocessing GGM bounds from one problem to another, also by means of simple reductions. Concretely, we prove novel preprocessing bounds on the hardness of the d-strong discrete logarithm, the d-strong Diffie-Hellman inversion, and multi-instance CDH problems, as well as a large class of Uber assumptions. Additionally, our approach applies to Shoup’s GGM without additional restrictions on the query behavior of the adversary, while the recent works of Zhang, Zhou, and Katz [AC22] and Zhandry [Crypto22] highlight that this is not the case for the AGM approach." 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: Charlotte full_name: Hoffmann, Charlotte id: 0f78d746-dc7d-11ea-9b2f-83f92091afe7 last_name: Hoffmann orcid: 0000-0003-2027-5549 - first_name: Guillermo full_name: Pascual Perez, Guillermo id: 2D7ABD02-F248-11E8-B48F-1D18A9856A87 last_name: Pascual Perez orcid: 0000-0001-8630-415X citation: ama: 'Auerbach B, Hoffmann C, Pascual Perez G. Generic-group lower bounds via reductions between geometric-search problems: With and without preprocessing. In: 21st International Conference on Theory of Cryptography. Vol 14371. Springer Nature; 2023:301-330. doi:10.1007/978-3-031-48621-0_11' apa: 'Auerbach, B., Hoffmann, C., & Pascual Perez, G. (2023). Generic-group lower bounds via reductions between geometric-search problems: With and without preprocessing. In 21st International Conference on Theory of Cryptography (Vol. 14371, pp. 301–330). Springer Nature. https://doi.org/10.1007/978-3-031-48621-0_11' chicago: 'Auerbach, Benedikt, Charlotte Hoffmann, and Guillermo Pascual Perez. “Generic-Group Lower Bounds via Reductions between Geometric-Search Problems: With and without Preprocessing.” In 21st International Conference on Theory of Cryptography, 14371:301–30. Springer Nature, 2023. https://doi.org/10.1007/978-3-031-48621-0_11.' ieee: 'B. Auerbach, C. Hoffmann, and G. Pascual Perez, “Generic-group lower bounds via reductions between geometric-search problems: With and without preprocessing,” in 21st International Conference on Theory of Cryptography, 2023, vol. 14371, pp. 301–330.' ista: 'Auerbach B, Hoffmann C, Pascual Perez G. 2023. Generic-group lower bounds via reductions between geometric-search problems: With and without preprocessing. 21st International Conference on Theory of Cryptography. , LNCS, vol. 14371, 301–330.' mla: 'Auerbach, Benedikt, et al. “Generic-Group Lower Bounds via Reductions between Geometric-Search Problems: With and without Preprocessing.” 21st International Conference on Theory of Cryptography, vol. 14371, Springer Nature, 2023, pp. 301–30, doi:10.1007/978-3-031-48621-0_11.' short: B. Auerbach, C. Hoffmann, G. Pascual Perez, in:, 21st International Conference on Theory of Cryptography, Springer Nature, 2023, pp. 301–330. date_created: 2023-12-17T23:00:54Z date_published: 2023-11-27T00:00:00Z date_updated: 2023-12-18T09:17:03Z day: '27' department: - _id: KrPi doi: 10.1007/978-3-031-48621-0_11 intvolume: ' 14371' language: - iso: eng main_file_link: - open_access: '1' url: https://eprint.iacr.org/2023/808 month: '11' oa: 1 oa_version: Preprint page: 301-330 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: 'Generic-group lower bounds via reductions between geometric-search problems: With and without preprocessing' type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 14371 year: '2023' ... --- _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' ... --- _id: '9826' abstract: - lang: eng text: "Automated contract tracing aims at supporting manual contact tracing during pandemics by alerting users of encounters with infected people. There are currently many proposals for protocols (like the “decentralized” DP-3T and PACT or the “centralized” ROBERT and DESIRE) to be run on mobile phones, where the basic idea is to regularly broadcast (using low energy Bluetooth) some values, and at the same time store (a function of) incoming messages broadcasted by users in their proximity. In the existing proposals one can trigger false positives on a massive scale by an “inverse-Sybil” attack, where a large number of devices (malicious users or hacked phones) pretend to be the same user, such that later, just a single person needs to be diagnosed (and allowed to upload) to trigger an alert for all users who were in proximity to any of this large group of devices.\r\n\r\nWe propose the first protocols that do not succumb to such attacks assuming the devices involved in the attack do not constantly communicate, which we observe is a necessary assumption. The high level idea of the protocols is to derive the values to be broadcasted by a hash chain, so that two (or more) devices who want to launch an inverse-Sybil attack will not be able to connect their respective chains and thus only one of them will be able to upload. Our protocols also achieve security against replay, belated replay, and one of them even against relay attacks." acknowledgement: Guillermo Pascual-Perez and Michelle Yeo were funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska–Curie Grant Agreement No. 665385; the remaining contributors to this project have received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT). 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: Suvradip full_name: Chakraborty, Suvradip id: B9CD0494-D033-11E9-B219-A439E6697425 last_name: Chakraborty - 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 id: 488F98B0-F248-11E8-B48F-1D18A9856A87 last_name: Walter orcid: 0000-0003-3186-2482 - first_name: Michelle X full_name: Yeo, Michelle X id: 2D82B818-F248-11E8-B48F-1D18A9856A87 last_name: Yeo citation: ama: 'Auerbach B, Chakraborty S, Klein K, et al. Inverse-Sybil attacks in automated contact tracing. In: Topics in Cryptology – CT-RSA 2021. Vol 12704. Springer Nature; 2021:399-421. doi:10.1007/978-3-030-75539-3_17' apa: 'Auerbach, B., Chakraborty, S., Klein, K., Pascual Perez, G., Pietrzak, K. Z., Walter, M., & Yeo, M. X. (2021). Inverse-Sybil attacks in automated contact tracing. In Topics in Cryptology – CT-RSA 2021 (Vol. 12704, pp. 399–421). Virtual Event: Springer Nature. https://doi.org/10.1007/978-3-030-75539-3_17' chicago: Auerbach, Benedikt, Suvradip Chakraborty, Karen Klein, Guillermo Pascual Perez, Krzysztof Z Pietrzak, Michael Walter, and Michelle X Yeo. “Inverse-Sybil Attacks in Automated Contact Tracing.” In Topics in Cryptology – CT-RSA 2021, 12704:399–421. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-75539-3_17. ieee: B. Auerbach et al., “Inverse-Sybil attacks in automated contact tracing,” in Topics in Cryptology – CT-RSA 2021, Virtual Event, 2021, vol. 12704, pp. 399–421. ista: 'Auerbach B, Chakraborty S, Klein K, Pascual Perez G, Pietrzak KZ, Walter M, Yeo MX. 2021. Inverse-Sybil attacks in automated contact tracing. Topics in Cryptology – CT-RSA 2021. CT-RSA: Cryptographers’ Track at the RSA Conference, LNCS, vol. 12704, 399–421.' mla: Auerbach, Benedikt, et al. “Inverse-Sybil Attacks in Automated Contact Tracing.” Topics in Cryptology – CT-RSA 2021, vol. 12704, Springer Nature, 2021, pp. 399–421, doi:10.1007/978-3-030-75539-3_17. short: B. Auerbach, S. Chakraborty, K. Klein, G. Pascual Perez, K.Z. Pietrzak, M. Walter, M.X. Yeo, in:, Topics in Cryptology – CT-RSA 2021, Springer Nature, 2021, pp. 399–421. conference: end_date: 2021-05-20 location: Virtual Event name: 'CT-RSA: Cryptographers’ Track at the RSA Conference' start_date: 2021-05-17 date_created: 2021-08-08T22:01:30Z date_published: 2021-05-11T00:00:00Z date_updated: 2023-02-23T14:09:56Z day: '11' department: - _id: KrPi - _id: GradSch doi: 10.1007/978-3-030-75539-3_17 ec_funded: 1 intvolume: ' 12704' language: - iso: eng main_file_link: - open_access: '1' url: https://eprint.iacr.org/2020/670 month: '05' oa: 1 oa_version: Submitted Version page: 399-421 project: - _id: 2564DBCA-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '665385' name: International IST Doctoral Program - _id: 258AA5B2-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '682815' name: Teaching Old Crypto New Tricks publication: Topics in Cryptology – CT-RSA 2021 publication_identifier: eissn: - '16113349' isbn: - '9783030755386' issn: - '03029743' publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: Inverse-Sybil attacks in automated contact tracing type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 12704 year: '2021' ... --- _id: '10408' abstract: - lang: eng text: 'Key trees are often the best solution in terms of transmission cost and storage requirements for managing keys in a setting where a group needs to share a secret key, while being able to efficiently rotate the key material of users (in order to recover from a potential compromise, or to add or remove users). Applications include multicast encryption protocols like LKH (Logical Key Hierarchies) or group messaging like the current IETF proposal TreeKEM. A key tree is a (typically balanced) binary tree, where each node is identified with a key: leaf nodes hold users’ secret keys while the root is the shared group key. For a group of size N, each user just holds log(N) keys (the keys on the path from its leaf to the root) and its entire key material can be rotated by broadcasting 2log(N) ciphertexts (encrypting each fresh key on the path under the keys of its parents). In this work we consider the natural setting where we have many groups with partially overlapping sets of users, and ask if we can find solutions where the cost of rotating a key is better than in the trivial one where we have a separate key tree for each group. We show that in an asymptotic setting (where the number m of groups is fixed while the number N of users grows) there exist more general key graphs whose cost converges to the cost of a single group, thus saving a factor linear in the number of groups over the trivial solution. As our asymptotic “solution” converges very slowly and performs poorly on concrete examples, we propose an algorithm that uses a natural heuristic to compute a key graph for any given group structure. Our algorithm combines two greedy algorithms, and is thus very efficient: it first converts the group structure into a “lattice graph”, which is then turned into a key graph by repeatedly applying the algorithm for constructing a Huffman code. To better understand how far our proposal is from an optimal solution, we prove lower bounds on the update cost of continuous group-key agreement and multicast encryption in a symbolic model admitting (asymmetric) encryption, pseudorandom generators, and secret sharing as building blocks.' acknowledgement: B. Auerbach, M.A. Baig and K. Pietrzak—received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT); Karen Klein was supported in part by ERC CoG grant 724307 and conducted part of this work at IST Austria, funded by the ERC under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT); Guillermo Pascual-Perez was funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 665385; Michael Walter conducted part of this work at IST Austria, funded by the ERC under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT). alternative_title: - LNCS article_processing_charge: No author: - first_name: Joel F full_name: Alwen, Joel F id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87 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: Mirza Ahad full_name: Baig, Mirza Ahad id: 3EDE6DE4-AA5A-11E9-986D-341CE6697425 last_name: Baig - 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 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 id: 488F98B0-F248-11E8-B48F-1D18A9856A87 last_name: Walter orcid: 0000-0003-3186-2482 citation: ama: 'Alwen JF, Auerbach B, Baig MA, et al. Grafting key trees: Efficient key management for overlapping groups. In: 19th International Conference. Vol 13044. Springer Nature; 2021:222-253. doi:10.1007/978-3-030-90456-2_8' apa: 'Alwen, J. F., Auerbach, B., Baig, M. A., Cueto Noval, M., Klein, K., Pascual Perez, G., … Walter, M. (2021). Grafting key trees: Efficient key management for overlapping groups. In 19th International Conference (Vol. 13044, pp. 222–253). Raleigh, NC, United States: Springer Nature. https://doi.org/10.1007/978-3-030-90456-2_8' chicago: 'Alwen, Joel F, Benedikt Auerbach, Mirza Ahad Baig, Miguel Cueto Noval, Karen Klein, Guillermo Pascual Perez, Krzysztof Z Pietrzak, and Michael Walter. “Grafting Key Trees: Efficient Key Management for Overlapping Groups.” In 19th International Conference, 13044:222–53. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-90456-2_8.' ieee: 'J. F. Alwen et al., “Grafting key trees: Efficient key management for overlapping groups,” in 19th International Conference, Raleigh, NC, United States, 2021, vol. 13044, pp. 222–253.' ista: 'Alwen JF, Auerbach B, Baig MA, Cueto Noval M, Klein K, Pascual Perez G, Pietrzak KZ, Walter M. 2021. Grafting key trees: Efficient key management for overlapping groups. 19th International Conference. TCC: Theory of Cryptography, LNCS, vol. 13044, 222–253.' mla: 'Alwen, Joel F., et al. “Grafting Key Trees: Efficient Key Management for Overlapping Groups.” 19th International Conference, vol. 13044, Springer Nature, 2021, pp. 222–53, doi:10.1007/978-3-030-90456-2_8.' short: J.F. Alwen, B. Auerbach, M.A. Baig, M. Cueto Noval, K. Klein, G. Pascual Perez, K.Z. Pietrzak, M. Walter, in:, 19th International Conference, Springer Nature, 2021, pp. 222–253. conference: end_date: 2021-11-11 location: Raleigh, NC, United States name: 'TCC: Theory of Cryptography' start_date: 2021-11-08 date_created: 2021-12-05T23:01:42Z date_published: 2021-11-04T00:00:00Z date_updated: 2023-08-14T13:19:39Z day: '04' department: - _id: KrPi doi: 10.1007/978-3-030-90456-2_8 ec_funded: 1 external_id: isi: - '000728363700008' intvolume: ' 13044' isi: 1 language: - iso: eng main_file_link: - open_access: '1' url: https://eprint.iacr.org/2021/1158 month: '11' oa: 1 oa_version: Preprint page: 222-253 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: 19th International Conference publication_identifier: eisbn: - 978-3-030-90456-2 eissn: - 1611-3349 isbn: - 9-783-0309-0455-5 issn: - 0302-9743 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: 'Grafting key trees: Efficient key management for overlapping groups' type: conference user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8 volume: 13044 year: '2021' ... --- _id: '7966' abstract: - lang: eng text: "For 1≤m≤n, we consider a natural m-out-of-n multi-instance scenario for a public-key encryption (PKE) scheme. An adversary, given n independent instances of PKE, wins if he breaks at least m out of the n instances. In this work, we are interested in the scaling factor of PKE schemes, SF, which measures how well the difficulty of breaking m out of the n instances scales in m. That is, a scaling factor SF=ℓ indicates that breaking m out of n instances is at least ℓ times more difficult than breaking one single instance. A PKE scheme with small scaling factor hence provides an ideal target for mass surveillance. In fact, the Logjam attack (CCS 2015) implicitly exploited, among other things, an almost constant scaling factor of ElGamal over finite fields (with shared group parameters).\r\n\r\nFor Hashed ElGamal over elliptic curves, we use the generic group model to argue that the scaling factor depends on the scheme's granularity. In low granularity, meaning each public key contains its independent group parameter, the scheme has optimal scaling factor SF=m; In medium and high granularity, meaning all public keys share the same group parameter, the scheme still has a reasonable scaling factor SF=√m. Our findings underline that instantiating ElGamal over elliptic curves should be preferred to finite fields in a multi-instance scenario.\r\n\r\nAs our main technical contribution, we derive new generic-group lower bounds of Ω(√(mp)) on the difficulty of solving both the m-out-of-n Gap Discrete Logarithm and the m-out-of-n Gap Computational Diffie-Hellman problem over groups of prime order p, extending a recent result by Yun (EUROCRYPT 2015). We establish the lower bound by studying the hardness of a related computational problem which we call the search-by-hypersurface problem." 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: Federico full_name: Giacon, Federico last_name: Giacon - first_name: Eike full_name: Kiltz, Eike last_name: Kiltz citation: ama: 'Auerbach B, Giacon F, Kiltz E. Everybody’s a target: Scalability in public-key encryption. In: Advances in Cryptology – EUROCRYPT 2020. Vol 12107. Springer Nature; 2020:475-506. doi:10.1007/978-3-030-45727-3_16' apa: 'Auerbach, B., Giacon, F., & Kiltz, E. (2020). Everybody’s a target: Scalability in public-key encryption. In Advances in Cryptology – EUROCRYPT 2020 (Vol. 12107, pp. 475–506). Springer Nature. https://doi.org/10.1007/978-3-030-45727-3_16' chicago: 'Auerbach, Benedikt, Federico Giacon, and Eike Kiltz. “Everybody’s a Target: Scalability in Public-Key Encryption.” In Advances in Cryptology – EUROCRYPT 2020, 12107:475–506. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-45727-3_16.' ieee: 'B. Auerbach, F. Giacon, and E. Kiltz, “Everybody’s a target: Scalability in public-key encryption,” in Advances in Cryptology – EUROCRYPT 2020, 2020, vol. 12107, pp. 475–506.' ista: 'Auerbach B, Giacon F, Kiltz E. 2020. Everybody’s a target: Scalability in public-key encryption. Advances in Cryptology – EUROCRYPT 2020. EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS, vol. 12107, 475–506.' mla: 'Auerbach, Benedikt, et al. “Everybody’s a Target: Scalability in Public-Key Encryption.” Advances in Cryptology – EUROCRYPT 2020, vol. 12107, Springer Nature, 2020, pp. 475–506, doi:10.1007/978-3-030-45727-3_16.' short: B. Auerbach, F. Giacon, E. Kiltz, in:, Advances in Cryptology – EUROCRYPT 2020, Springer Nature, 2020, pp. 475–506. conference: end_date: 2020-05-15 name: 'EUROCRYPT: Theory and Applications of Cryptographic Techniques' start_date: 2020-05-11 date_created: 2020-06-15T07:13:37Z date_published: 2020-05-01T00:00:00Z date_updated: 2023-09-05T15:06:40Z day: '01' department: - _id: KrPi doi: 10.1007/978-3-030-45727-3_16 ec_funded: 1 external_id: isi: - '000828688000016' intvolume: ' 12107' isi: 1 language: - iso: eng main_file_link: - open_access: '1' url: https://eprint.iacr.org/2019/364 month: '05' oa: 1 oa_version: Submitted Version page: 475-506 project: - _id: 258AA5B2-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '682815' name: Teaching Old Crypto New Tricks publication: Advances in Cryptology – EUROCRYPT 2020 publication_identifier: eissn: - 1611-3349 isbn: - '9783030457266' - '9783030457273' issn: - 0302-9743 publication_status: published publisher: Springer Nature quality_controlled: '1' status: public title: 'Everybody’s a target: Scalability in public-key encryption' type: conference user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 volume: 12107 year: '2020' ...