[{"cryptoeprintid":1,"month":"01","page":"6699-6716","year":"2025","has_accepted_license":"1","publisher":"Usenix Association","conference":{"start_date":"2025-08-13","location":"Seattle, WA, USA","end_date":"2025-08-15","name":"USENIX: Security Symposium"},"date_published":"2025-01-01T00:00:00Z","day":"01","quality_controlled":"1","publication":"34th Usenix Security Symposium","file_date_updated":"2025-11-24T07:44:08Z","title":"Exploring how to authenticate application messages in MLS: More efficient, post-quantum, and anonymous blocklistable","corr_author":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","scopus_import":"1","author":[{"first_name":"Keitaro","last_name":"Hashimoto","full_name":"Hashimoto, Keitaro"},{"full_name":"Katsumata, Shuichi","last_name":"Katsumata","first_name":"Shuichi"},{"id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8630-415X","full_name":"Pascual Perez, Guillermo","last_name":"Pascual Perez","first_name":"Guillermo"}],"citation":{"mla":"Hashimoto, Keitaro, et al. “Exploring How to Authenticate Application Messages in MLS: More Efficient, Post-Quantum, and Anonymous Blocklistable.” <i>34th Usenix Security Symposium</i>, Usenix Association, 2025, pp. 6699–716.","short":"K. Hashimoto, S. Katsumata, G. Pascual Perez, in:, 34th Usenix Security Symposium, Usenix Association, 2025, pp. 6699–6716.","ama":"Hashimoto K, Katsumata S, Pascual Perez G. Exploring how to authenticate application messages in MLS: More efficient, post-quantum, and anonymous blocklistable. In: <i>34th Usenix Security Symposium</i>. Usenix Association; 2025:6699-6716.","ieee":"K. Hashimoto, S. Katsumata, and G. Pascual Perez, “Exploring how to authenticate application messages in MLS: More efficient, post-quantum, and anonymous blocklistable,” in <i>34th Usenix Security Symposium</i>, Seattle, WA, USA, 2025, pp. 6699–6716.","chicago":"Hashimoto, Keitaro, Shuichi Katsumata, and Guillermo Pascual Perez. “Exploring How to Authenticate Application Messages in MLS: More Efficient, Post-Quantum, and Anonymous Blocklistable.” In <i>34th Usenix Security Symposium</i>, 6699–6716. Usenix Association, 2025.","apa":"Hashimoto, K., Katsumata, S., &#38; Pascual Perez, G. (2025). Exploring how to authenticate application messages in MLS: More efficient, post-quantum, and anonymous blocklistable. In <i>34th Usenix Security Symposium</i> (pp. 6699–6716). Seattle, WA, USA: Usenix Association.","ista":"Hashimoto K, Katsumata S, Pascual Perez G. 2025. Exploring how to authenticate application messages in MLS: More efficient, post-quantum, and anonymous blocklistable. 34th Usenix Security Symposium. USENIX: Security Symposium, 6699–6716."},"abstract":[{"lang":"eng","text":"The Message Layer Security (MLS) protocol has recently been standardized by the IETF. MLS is a scalable secure group messaging protocol expected to run more efficiently compared to the Signal protocol at scale, while offering a similar level of strong security. Even though MLS has undergone extensive examination by researchers, the majority of the works have focused on confidentiality.\r\n\r\nIn this work, we focus on the authenticity of the application messages exchanged in MLS. Currently, MLS authenticates every application message with an EdDSA signature and while manageable, the overhead is greatly amplified in the post-quantum setting as the NIST-recommended Dilithium signature results in a 40x increase in size. We view this as an invitation to explore new authentication modes that can be used instead. We start by taking a systematic view on how application messages are authenticated in MLS and categorize authenticity into four different security notions. We then propose several authentication modes, offering a range of different efficiency and security profiles. For instance, in one of our modes, COSMOS++, we replace signatures with one-time tokens and a MAC tag, offering roughly a 75x savings in the post-quantum communication overhead. While this comes at the cost of weakening security compared to the authentication mode used by MLS, the lower communication overhead seems to make it a worthwhile trade-off with security."}],"article_processing_charge":"No","date_created":"2025-11-23T23:01:40Z","main_file_link":[{"url":"https://eprint.iacr.org/2025/426","open_access":"1"}],"publication_status":"published","_id":"20668","date_updated":"2026-07-07T06:02:03Z","status":"public","language":[{"iso":"eng"}],"oa":1,"publication_identifier":{"isbn":["9781939133526"]},"ddc":["000"],"project":[{"grant_number":"665385","call_identifier":"H2020","name":"International IST Doctoral Program","_id":"2564DBCA-B435-11E9-9278-68D0E5697425"}],"external_id":{"cryptoeprintid":["2025/426"]},"ec_funded":1,"OA_place":"publisher","file":[{"creator":"dernst","file_id":"20671","content_type":"application/pdf","file_name":"2025_Usenix_Hashimoto.pdf","access_level":"open_access","date_created":"2025-11-24T07:44:08Z","file_size":710733,"success":1,"checksum":"fcfe8851aeb751af98c0b1335a0ef149","relation":"main_file","date_updated":"2025-11-24T07:44:08Z"}],"acknowledgement":"This research was partially supported by JST CREST JPMJCR22M1, Japan and funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No.665385.","OA_type":"diamond","das_tickbox":"1","oa_version":"Published Version","type":"conference"},{"status":"public","language":[{"iso":"eng"}],"date_updated":"2025-12-02T13:55:46Z","_id":"18702","oa":1,"isi":1,"publication_identifier":{"isbn":["9783031780103"],"eissn":["1611-3349"],"issn":["0302-9743"]},"department":[{"_id":"MaKw"},{"_id":"KrPi"}],"external_id":{"isi":["001545628900014"]},"OA_place":"repository","type":"conference","oa_version":"Preprint","OA_type":"green","doi":"10.1007/978-3-031-78011-0_14","publisher":"Springer Nature","volume":15364,"month":"12","year":"2024","page":"413-443","conference":{"end_date":"2024-12-06","name":"TCC: Theory of Cryptography","location":"Milan, Italy","start_date":"2024-12-02"},"date_published":"2024-12-02T00:00:00Z","day":"02","alternative_title":["LNCS"],"title":"The cost of maintaining keys in dynamic groups with applications to multicast encryption and group messaging","intvolume":"     15364","quality_controlled":"1","publication":"22nd International Conference on Theory of Cryptography","corr_author":"1","abstract":[{"text":"In this work we prove lower bounds on the (communication) cost of maintaining a shared key among a dynamic group of users. Being “dynamic” means one can add and remove users from the group. This captures important protocols like multicast encryption (ME) and continuous group-key agreement (CGKA), which is the primitive underlying many group messaging applications. We prove our bounds in a combinatorial setting where the state of the protocol progresses in rounds. The state of the protocol in each round is captured by a set system, with each of its elements specifying a set of users who share a secret key. We show this combinatorial model implies bounds in symbolic models for ME and CGKA that capture, as building blocks, PRGs, PRFs, dual PRFs, secret sharing, and symmetric encryption in the setting of ME, and PRGs, PRFs, dual PRFs, secret sharing, public-key encryption, and key-updatable public-key encryption in the setting of CGKA. The models are related to the ones used by Micciancio and Panjwani (Eurocrypt’04) and Bienstock et al. (TCC’20) to analyze ME and CGKA, respectively. We prove – using the Bollobás’ Set Pairs Inequality – that the cost (number of uploaded ciphertexts) for replacing a set of d users in a group of size n is Ω(dln(n/d)). Our lower bound is asymptotically tight and both improves on a bound of Ω(d) by Bienstock et al. (TCC’20), and generalizes a result by Micciancio and Panjwani (Eurocrypt’04), who proved a lower bound of Ω(log(n)) for d=1. ","lang":"eng"}],"citation":{"mla":"Anastos, Michael, et al. “The Cost of Maintaining Keys in Dynamic Groups with Applications to Multicast Encryption and Group Messaging.” <i>22nd International Conference on Theory of Cryptography</i>, vol. 15364, Springer Nature, 2024, pp. 413–43, doi:<a href=\"https://doi.org/10.1007/978-3-031-78011-0_14\">10.1007/978-3-031-78011-0_14</a>.","chicago":"Anastos, Michael, Benedikt Auerbach, Mirza Ahad Baig, Miguel Cueto Noval, Matthew Alan Kwan, Guillermo Pascual Perez, and Krzysztof Z Pietrzak. “The Cost of Maintaining Keys in Dynamic Groups with Applications to Multicast Encryption and Group Messaging.” In <i>22nd International Conference on Theory of Cryptography</i>, 15364:413–43. Springer Nature, 2024. <a href=\"https://doi.org/10.1007/978-3-031-78011-0_14\">https://doi.org/10.1007/978-3-031-78011-0_14</a>.","ieee":"M. Anastos <i>et al.</i>, “The cost of maintaining keys in dynamic groups with applications to multicast encryption and group messaging,” in <i>22nd International Conference on Theory of Cryptography</i>, Milan, Italy, 2024, vol. 15364, pp. 413–443.","ista":"Anastos M, Auerbach B, Baig MA, Cueto Noval M, Kwan MA, Pascual Perez G, Pietrzak KZ. 2024. The cost of maintaining keys in dynamic groups with applications to multicast encryption and group messaging. 22nd International Conference on Theory of Cryptography. TCC: Theory of Cryptography, LNCS, vol. 15364, 413–443.","apa":"Anastos, M., Auerbach, B., Baig, M. A., Cueto Noval, M., Kwan, M. A., Pascual Perez, G., &#38; Pietrzak, K. Z. (2024). The cost of maintaining keys in dynamic groups with applications to multicast encryption and group messaging. In <i>22nd International Conference on Theory of Cryptography</i> (Vol. 15364, pp. 413–443). Milan, Italy: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-78011-0_14\">https://doi.org/10.1007/978-3-031-78011-0_14</a>","short":"M. Anastos, B. Auerbach, M.A. Baig, M. Cueto Noval, M.A. Kwan, G. Pascual Perez, K.Z. Pietrzak, in:, 22nd International Conference on Theory of Cryptography, Springer Nature, 2024, pp. 413–443.","ama":"Anastos M, Auerbach B, Baig MA, et al. The cost of maintaining keys in dynamic groups with applications to multicast encryption and group messaging. In: <i>22nd International Conference on Theory of Cryptography</i>. Vol 15364. Springer Nature; 2024:413-443. doi:<a href=\"https://doi.org/10.1007/978-3-031-78011-0_14\">10.1007/978-3-031-78011-0_14</a>"},"publication_status":"published","date_created":"2024-12-22T23:01:47Z","main_file_link":[{"url":"https://eprint.iacr.org/2024/1097","open_access":"1"}],"article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","scopus_import":"1","author":[{"id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","full_name":"Anastos, Michael","last_name":"Anastos","first_name":"Michael"},{"first_name":"Benedikt","last_name":"Auerbach","full_name":"Auerbach, Benedikt","orcid":"0000-0002-7553-6606","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425"},{"first_name":"Mirza Ahad","id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425","full_name":"Baig, Mirza Ahad","last_name":"Baig"},{"first_name":"Miguel","orcid":"0000-0002-2505-4246","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","last_name":"Cueto Noval","full_name":"Cueto Noval, Miguel"},{"first_name":"Matthew Alan","last_name":"Kwan","full_name":"Kwan, Matthew Alan","orcid":"0000-0002-4003-7567","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3"},{"first_name":"Guillermo","last_name":"Pascual Perez","full_name":"Pascual Perez, Guillermo","orcid":"0000-0001-8630-415X","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z"}]},{"external_id":{"isi":["001330408000014"]},"place":"Cham","department":[{"_id":"GradSch"},{"_id":"KrPi"}],"related_material":{"record":[{"status":"public","id":"18088","relation":"dissertation_contains"}]},"type":"conference","oa_version":"None","_id":"18086","date_updated":"2026-04-07T13:01:26Z","language":[{"iso":"eng"}],"status":"public","isi":1,"publication_identifier":{"isbn":["9783031710728"],"issn":["0302-9743"],"eissn":["1611-3349"],"eisbn":["9783031710735"]},"publication":"Security and Cryptography for Networks: 14th International Conference","quality_controlled":"1","title":"DeCAF: Decentralizable CGKA with fast healing","intvolume":"     14974","editor":[{"full_name":"Galdi, Clemente","last_name":"Galdi","first_name":"Clemente"},{"first_name":"Duong Hieu","last_name":"Phan","full_name":"Phan, Duong Hieu"}],"corr_author":"1","citation":{"ieee":"J. F. Alwen, B. Auerbach, M. Cueto Noval, K. Klein, G. Pascual Perez, and K. Z. Pietrzak, “DeCAF: Decentralizable CGKA with fast healing,” in <i>Security and Cryptography for Networks: 14th International Conference</i>, Amalfi, Italy, 2024, vol. 14974, pp. 294–313.","chicago":"Alwen, Joel F, Benedikt Auerbach, Miguel Cueto Noval, Karen Klein, Guillermo Pascual Perez, and Krzysztof Z Pietrzak. “DeCAF: Decentralizable CGKA with Fast Healing.” In <i>Security and Cryptography for Networks: 14th International Conference</i>, edited by Clemente Galdi and Duong Hieu Phan, 14974:294–313. Cham: Springer Nature, 2024. <a href=\"https://doi.org/10.1007/978-3-031-71073-5_14\">https://doi.org/10.1007/978-3-031-71073-5_14</a>.","apa":"Alwen, J. F., Auerbach, B., Cueto Noval, M., Klein, K., Pascual Perez, G., &#38; Pietrzak, K. Z. (2024). DeCAF: Decentralizable CGKA with fast healing. In C. Galdi &#38; D. H. Phan (Eds.), <i>Security and Cryptography for Networks: 14th International Conference</i> (Vol. 14974, pp. 294–313). Cham: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-71073-5_14\">https://doi.org/10.1007/978-3-031-71073-5_14</a>","ista":"Alwen JF, Auerbach B, Cueto Noval M, Klein K, Pascual Perez G, Pietrzak KZ. 2024. DeCAF: Decentralizable CGKA with fast healing. Security and Cryptography for Networks: 14th International Conference. SCN: Security and Cryptography for Networks, LNCS, vol. 14974, 294–313.","short":"J.F. Alwen, B. Auerbach, M. Cueto Noval, K. Klein, G. Pascual Perez, K.Z. Pietrzak, in:, C. Galdi, D.H. Phan (Eds.), Security and Cryptography for Networks: 14th International Conference, Springer Nature, Cham, 2024, pp. 294–313.","ama":"Alwen JF, Auerbach B, Cueto Noval M, Klein K, Pascual Perez G, Pietrzak KZ. DeCAF: Decentralizable CGKA with fast healing. In: Galdi C, Phan DH, eds. <i>Security and Cryptography for Networks: 14th International Conference</i>. Vol 14974. Cham: Springer Nature; 2024:294–313. doi:<a href=\"https://doi.org/10.1007/978-3-031-71073-5_14\">10.1007/978-3-031-71073-5_14</a>","mla":"Alwen, Joel F., et al. “DeCAF: Decentralizable CGKA with Fast Healing.” <i>Security and Cryptography for Networks: 14th International Conference</i>, edited by Clemente Galdi and Duong Hieu Phan, vol. 14974, Springer Nature, 2024, pp. 294–313, doi:<a href=\"https://doi.org/10.1007/978-3-031-71073-5_14\">10.1007/978-3-031-71073-5_14</a>."},"abstract":[{"text":"Abstract. Continuous group key agreement (CGKA) allows a group of\r\nusers to maintain a continuously updated shared key in an asynchronous\r\nsetting where parties only come online sporadically and their messages\r\nare relayed by an untrusted server. CGKA captures the basic primitive\r\nunderlying group messaging schemes.\r\nCurrent solutions including TreeKEM (“Messaging Layer Security”\r\n(MLS) IETF RFC 9420) cannot handle concurrent requests while retaining low communication complexity. The exception being CoCoA, which\r\nis concurrent while having extremely low communication complexity (in\r\ngroups of size n and for m concurrent updates the communication per\r\nuser is log(n), i.e., independent of m). The main downside of CoCoA\r\nis that in groups of size n, users might have to do up to log(n) update\r\nrequests to the server to ensure their (potentially corrupted) key material has been refreshed.\r\nIn this work we present a “fast healing” concurrent CGKA protocol,\r\nnamed DeCAF, where users will heal after at most log(t) requests, with\r\nt being the number of corrupted users. While also suitable for the standard central-server setting, our protocol is particularly interesting for\r\nrealizing decentralized group messaging, where protocol messages (add,\r\nremove, update) are being posted on some append-only data structure\r\nrather than sent to a server. In this setting, concurrency is crucial once\r\nthe rate of requests exceeds, say, the rate at which new blocks are added\r\nto a blockchain.\r\nIn the central-server setting, CoCoA (the only alternative with concurrency, sub-linear communication and basic post-compromise security)\r\nenjoys much lower download communication. However, in the decentralized setting – where there is no server which can craft specific messages\r\nfor different users to reduce their download communication – our protocol\r\nsignificantly outperforms CoCoA. DeCAF heals in fewer epochs (log(t)\r\nvs. log(n)) while incurring a similar per epoch per user communication\r\ncost.","lang":"eng"}],"date_created":"2024-09-18T11:35:14Z","article_processing_charge":"No","publication_status":"published","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","author":[{"last_name":"Alwen","full_name":"Alwen, Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","first_name":"Joel F"},{"orcid":"0000-0002-7553-6606","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","last_name":"Auerbach","full_name":"Auerbach, Benedikt","first_name":"Benedikt"},{"first_name":"Miguel","full_name":"Cueto Noval, Miguel","last_name":"Cueto Noval","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","orcid":"0000-0002-2505-4246"},{"first_name":"Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","full_name":"Klein, Karen","last_name":"Klein"},{"first_name":"Guillermo","last_name":"Pascual Perez","full_name":"Pascual Perez, Guillermo","orcid":"0000-0001-8630-415X","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z"}],"doi":"10.1007/978-3-031-71073-5_14","publisher":"Springer Nature","month":"09","volume":14974,"page":"294–313","year":"2024","conference":{"start_date":"2024-09-11","location":"Amalfi, Italy","name":"SCN: Security and Cryptography for Networks","end_date":"2024-09-13"},"day":"10","date_published":"2024-09-10T00:00:00Z","alternative_title":["LNCS"]},{"publisher":"Institute of Science and Technology Austria","doi":"10.15479/at:ista:18088","has_accepted_license":"1","year":"2024","page":"239","degree_awarded":"PhD","month":"09","day":"18","date_published":"2024-09-18T00:00:00Z","alternative_title":["ISTA Thesis"],"corr_author":"1","title":"On the efficiency and security of secure group messaging","file_date_updated":"2024-09-19T12:36:08Z","publication_status":"published","date_created":"2024-09-18T12:59:49Z","tmp":{"image":"/images/cc_by_nc_sa.png","legal_code_url":"https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode","name":"Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)","short":"CC BY-NC-SA (4.0)"},"article_processing_charge":"No","abstract":[{"lang":"eng","text":"Instant messaging applications like Whatsapp, Signal or Telegram have become ubiquitous in today's society.\r\nMany of them provide not only end-to-end encryption, but also security guarantees even when the key material gets compromised.\r\nThese are achieved through frequent key update performed by users.\r\nIn particular, the compromise of a group key should preserve confidentiality of previously exchanged messages (forward secrecy), and a subsequent key update will ensure security for future ones (post-compromise security).\r\nThough great protocols for one-on-one communication have been known for some time, the design of ones that scale efficiently for larger groups while achieving akin security guarantees is a hard problem.\r\nA great deal of research has been aimed at this topic, much of it under the umbrella of the Messaging Layer Security (MLS) working group at the IETF. \r\nStarted in 2018, this joint effort by academics and industry culminated in 2023 with the publication of the first standard for secure group messaging [IETF, RFC9420].\r\n\r\nAt the core of secure group messaging is a cryptographic primitive termed Continuous Group Key Agreement, or CGKA [Alwen et al. 2021], that essentially allows a changing group of users to agree on a common key with the added functionality security against compromises is achieved by users asynchronously issuing a key update. In this thesis we contribute to the understanding of CGKA across different angles.\r\nFirst, we present a new technique to effect dynamic operations in groups, i.e., add or remove members, that can be more efficient that the one employed by MLS in certain settings.\r\nConsidering the setting of users belonging to multiple overlapping groups, we then show lowerbounds on the communication cost of constructions that leverage said overlap, at the same time showing protocols that are asymptotically optimal and efficient for practical settings, respectively. Along the way, we show that the communication cost of key updates in MLS is average-cost optimal.\r\nAn important feature in CGKA protocols, particularly for big groups, is the possibility of executing several group operations concurrently. While later versions of MLS support this, they do at the cost of worsening the communication efficiency of future group operations.\r\nIn this thesis we introduce two new protocols that permit concurrency without any negative effect on efficiency. Our protocols circumvent previously existing lower bounds by satisfying a new notion of post-compromise security that only asks for security to be re-established after a certain number of key updates have taken place. While this can be slower than MLS in terms of rounds of communication, we show that it leads to more efficient overall communication. \r\nAdditionally, we introduce a new technique that allows group members to decrease the information they need to store and download, which makes one of our protocols enjoy much lower download cost than any other existing CGKA constructions. "}],"citation":{"ista":"Pascual Perez G. 2024. On the efficiency and security of secure group messaging. Institute of Science and Technology Austria.","apa":"Pascual Perez, G. (2024). <i>On the efficiency and security of secure group messaging</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/at:ista:18088\">https://doi.org/10.15479/at:ista:18088</a>","ieee":"G. Pascual Perez, “On the efficiency and security of secure group messaging,” Institute of Science and Technology Austria, 2024.","chicago":"Pascual Perez, Guillermo. “On the Efficiency and Security of Secure Group Messaging.” Institute of Science and Technology Austria, 2024. <a href=\"https://doi.org/10.15479/at:ista:18088\">https://doi.org/10.15479/at:ista:18088</a>.","ama":"Pascual Perez G. On the efficiency and security of secure group messaging. 2024. doi:<a href=\"https://doi.org/10.15479/at:ista:18088\">10.15479/at:ista:18088</a>","short":"G. Pascual Perez, On the Efficiency and Security of Secure Group Messaging, Institute of Science and Technology Austria, 2024.","mla":"Pascual Perez, Guillermo. <i>On the Efficiency and Security of Secure Group Messaging</i>. Institute of Science and Technology Austria, 2024, doi:<a href=\"https://doi.org/10.15479/at:ista:18088\">10.15479/at:ista:18088</a>."},"author":[{"first_name":"Guillermo","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8630-415X","full_name":"Pascual Perez, Guillermo","last_name":"Pascual Perez"}],"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","oa":1,"language":[{"iso":"eng"}],"status":"public","date_updated":"2026-04-07T13:01:26Z","_id":"18088","ddc":["000"],"publication_identifier":{"issn":["2663-337X"]},"file":[{"file_name":"thesis_bundle.zip","access_level":"closed","date_created":"2024-09-19T12:35:38Z","file_size":11917734,"creator":"gpascual","file_id":"18099","content_type":"application/x-zip-compressed","checksum":"ce0dca715b3df48e52e2e891b6ac1bc5","relation":"source_file","date_updated":"2024-09-19T12:35:38Z"},{"access_level":"open_access","file_name":"thesis_gpasper.pdf","date_created":"2024-09-19T12:36:08Z","file_size":2729427,"creator":"gpascual","file_id":"18100","content_type":"application/pdf","relation":"main_file","checksum":"4a2c72e90f1a0ef2a13cff800f8d1265","date_updated":"2024-09-19T12:36:08Z"}],"OA_place":"publisher","department":[{"_id":"KrPi"},{"_id":"GradSch"}],"ec_funded":1,"supervisor":[{"first_name":"Krzysztof Z","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"}],"related_material":{"record":[{"status":"public","relation":"part_of_dissertation","id":"10408"},{"relation":"part_of_dissertation","id":"11476","status":"public"},{"status":"public","id":"18086","relation":"part_of_dissertation"},{"relation":"part_of_dissertation","id":"10049","status":"public"}]},"project":[{"_id":"2564DBCA-B435-11E9-9278-68D0E5697425","name":"International IST Doctoral Program","call_identifier":"H2020","grant_number":"665385"}],"oa_version":"Published Version","type":"dissertation"},{"day":"27","date_published":"2023-11-27T00:00:00Z","conference":{"location":"Taipei, Taiwan","start_date":"2023-11-29","name":"TCC: Theory of Cryptography","end_date":"2023-12-02"},"alternative_title":["LNCS"],"publisher":"Springer Nature","doi":"10.1007/978-3-031-48621-0_10","year":"2023","page":"271-300","month":"11","volume":14371,"date_created":"2023-12-17T23:00:53Z","main_file_link":[{"url":"https://eprint.iacr.org/2023/1123","open_access":"1"}],"article_processing_charge":"No","publication_status":"published","citation":{"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>.","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.","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>","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.","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>"},"abstract":[{"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.","lang":"eng"}],"author":[{"full_name":"Auerbach, Benedikt","last_name":"Auerbach","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","orcid":"0000-0002-7553-6606","first_name":"Benedikt"},{"orcid":"0000-0002-2505-4246","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","last_name":"Cueto Noval","full_name":"Cueto Noval, Miguel","first_name":"Miguel"},{"full_name":"Pascual Perez, Guillermo","last_name":"Pascual Perez","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8630-415X","first_name":"Guillermo"},{"first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak"}],"scopus_import":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","corr_author":"1","quality_controlled":"1","publication":"21st International Conference on Theory of Cryptography","intvolume":"     14371","title":"On the cost of post-compromise security in concurrent Continuous Group-Key Agreement","publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["9783031486203"]},"oa":1,"isi":1,"_id":"14691","date_updated":"2025-09-09T13:42:16Z","language":[{"iso":"eng"}],"status":"public","oa_version":"Preprint","type":"conference","external_id":{"isi":["001160724400010"]},"department":[{"_id":"KrPi"}]},{"citation":{"mla":"Auerbach, Benedikt, et al. “Generic-Group Lower Bounds via Reductions between Geometric-Search Problems: With and without Preprocessing.” <i>21st International Conference on Theory of Cryptography</i>, vol. 14371, Springer Nature, 2023, pp. 301–30, doi:<a href=\"https://doi.org/10.1007/978-3-031-48621-0_11\">10.1007/978-3-031-48621-0_11</a>.","ama":"Auerbach B, Hoffmann C, Pascual Perez G. Generic-group lower bounds via reductions between geometric-search problems: With and without preprocessing. In: <i>21st International Conference on Theory of Cryptography</i>. Vol 14371. Springer Nature; 2023:301-330. doi:<a href=\"https://doi.org/10.1007/978-3-031-48621-0_11\">10.1007/978-3-031-48621-0_11</a>","short":"B. Auerbach, C. Hoffmann, G. Pascual Perez, in:, 21st International Conference on Theory of Cryptography, Springer Nature, 2023, 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.","apa":"Auerbach, B., Hoffmann, C., &#38; Pascual Perez, G. (2023). Generic-group lower bounds via reductions between geometric-search problems: With and without preprocessing. In <i>21st International Conference on Theory of Cryptography</i> (Vol. 14371, pp. 301–330). Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-48621-0_11\">https://doi.org/10.1007/978-3-031-48621-0_11</a>","chicago":"Auerbach, Benedikt, Charlotte Hoffmann, and Guillermo Pascual Perez. “Generic-Group Lower Bounds via Reductions between Geometric-Search Problems: With and without Preprocessing.” In <i>21st International Conference on Theory of Cryptography</i>, 14371:301–30. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/978-3-031-48621-0_11\">https://doi.org/10.1007/978-3-031-48621-0_11</a>.","ieee":"B. Auerbach, C. Hoffmann, and G. Pascual Perez, “Generic-group lower bounds via reductions between geometric-search problems: With and without preprocessing,” in <i>21st International Conference on Theory of Cryptography</i>, 2023, vol. 14371, pp. 301–330."},"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."}],"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2023/808"}],"article_processing_charge":"No","date_created":"2023-12-17T23:00:54Z","publication_status":"published","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","author":[{"orcid":"0000-0002-7553-6606","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","last_name":"Auerbach","full_name":"Auerbach, Benedikt","first_name":"Benedikt"},{"orcid":"0000-0003-2027-5549","id":"0f78d746-dc7d-11ea-9b2f-83f92091afe7","last_name":"Hoffmann","full_name":"Hoffmann, Charlotte","first_name":"Charlotte"},{"first_name":"Guillermo","orcid":"0000-0001-8630-415X","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","last_name":"Pascual Perez","full_name":"Pascual Perez, Guillermo"}],"scopus_import":"1","quality_controlled":"1","publication":"21st International Conference on Theory of Cryptography","title":"Generic-group lower bounds via reductions between geometric-search problems: With and without preprocessing","intvolume":"     14371","corr_author":"1","day":"27","date_published":"2023-11-27T00:00:00Z","alternative_title":["LNCS"],"doi":"10.1007/978-3-031-48621-0_11","publisher":"Springer Nature","month":"11","volume":14371,"page":"301-330","year":"2023","oa_version":"Preprint","type":"conference","external_id":{"isi":["001160724400011"]},"department":[{"_id":"KrPi"}],"publication_identifier":{"issn":["0302-9743"],"eissn":["1611-3349"],"isbn":["9783031486203"]},"_id":"14692","date_updated":"2025-09-09T14:02:04Z","status":"public","language":[{"iso":"eng"}],"oa":1,"isi":1},{"oa":1,"isi":1,"status":"public","language":[{"iso":"eng"}],"date_updated":"2026-04-07T13:01:26Z","_id":"11476","publication_identifier":{"eissn":["1611-3349"],"eisbn":["9783031070853"],"issn":["0302-9743"],"isbn":["9783031070846"]},"ec_funded":1,"department":[{"_id":"GradSch"},{"_id":"KrPi"}],"place":"Cham","external_id":{"isi":["000832305300028"]},"project":[{"grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks"},{"name":"International IST Doctoral Program","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","grant_number":"665385","call_identifier":"H2020"}],"related_material":{"record":[{"status":"public","id":"18088","relation":"dissertation_contains"}]},"type":"conference","oa_version":"Preprint","acknowledgement":"We thank Marta Mularczyk and Yiannis Tselekounis for their very helpful feedback on an earlier draft of this paper.","publisher":"Springer Nature","doi":"10.1007/978-3-031-07085-3_28","year":"2022","page":"815–844","volume":13276,"month":"05","day":"25","date_published":"2022-05-25T00:00:00Z","conference":{"location":"Trondheim, Norway","start_date":"2022-05-30","name":"EUROCRYPT: Theory and Applications of Cryptology and Information Security","end_date":"2022-06-03"},"alternative_title":["LNCS"],"corr_author":"1","title":"CoCoA: Concurrent continuous group key agreement","intvolume":"     13276","publication":"Advances in Cryptology – EUROCRYPT 2022","quality_controlled":"1","publication_status":"published","main_file_link":[{"url":"https://eprint.iacr.org/2022/251","open_access":"1"}],"date_created":"2022-06-30T16:48:00Z","article_processing_charge":"No","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."}],"citation":{"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>","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.","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.","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>","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.","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>."},"scopus_import":"1","author":[{"first_name":"Joël","full_name":"Alwen, Joël","last_name":"Alwen"},{"first_name":"Benedikt","last_name":"Auerbach","full_name":"Auerbach, Benedikt","orcid":"0000-0002-7553-6606","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425"},{"last_name":"Cueto Noval","full_name":"Cueto Noval, Miguel","orcid":"0000-0002-2505-4246","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","first_name":"Miguel"},{"full_name":"Klein, Karen","last_name":"Klein","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","first_name":"Karen"},{"first_name":"Guillermo","last_name":"Pascual Perez","full_name":"Pascual Perez, Guillermo","orcid":"0000-0001-8630-415X","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z"},{"last_name":"Walter","full_name":"Walter, Michael","first_name":"Michael"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"corr_author":"1","title":"Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement","quality_controlled":"1","publication":"2021 IEEE Symposium on Security and Privacy ","publication_status":"published","date_created":"2021-09-27T13:46:27Z","main_file_link":[{"url":"https://eprint.iacr.org/2019/1489","open_access":"1"}],"article_processing_charge":"No","abstract":[{"lang":"eng","text":"While messaging systems with strong security guarantees are widely used in practice, designing a protocol that scales efficiently to large groups and enjoys similar security guarantees remains largely open. The two existing proposals to date are ART (Cohn-Gordon et al., CCS18) and TreeKEM (IETF, The Messaging Layer Security Protocol, draft). TreeKEM is the currently considered candidate by the IETF MLS working group, but dynamic group operations (i.e. adding and removing users) can cause efficiency issues. In this paper we formalize and analyze a variant of TreeKEM which we term Tainted TreeKEM (TTKEM for short). The basic idea underlying TTKEM was suggested by Millican (MLS mailing list, February 2018). This version is more efficient than TreeKEM for some natural distributions of group operations, we quantify this through simulations.Our second contribution is two security proofs for TTKEM which establish post compromise and forward secrecy even against adaptive attackers. The security loss (to the underlying PKE) in the Random Oracle Model is a polynomial factor, and a quasipolynomial one in the Standard Model. Our proofs can be adapted to TreeKEM as well. Before our work no security proof for any TreeKEM-like protocol establishing tight security against an adversary who can adaptively choose the sequence of operations was known. We also are the first to prove (or even formalize) active security where the server can arbitrarily deviate from the protocol specification. Proving fully active security – where also the users can arbitrarily deviate – remains open."}],"citation":{"short":"K. Klein, G. Pascual Perez, M. Walter, C. Kamath Hosdurg, M. Capretto, M. Cueto Noval, I. Markov, M.X. Yeo, J.F. Alwen, K.Z. Pietrzak, in:, 2021 IEEE Symposium on Security and Privacy , IEEE, 2021, pp. 268–284.","ama":"Klein K, Pascual Perez G, Walter M, et al. Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement. In: <i>2021 IEEE Symposium on Security and Privacy </i>. IEEE; 2021:268-284. doi:<a href=\"https://doi.org/10.1109/sp40001.2021.00035\">10.1109/sp40001.2021.00035</a>","chicago":"Klein, Karen, Guillermo Pascual Perez, Michael Walter, Chethan Kamath Hosdurg, Margarita Capretto, Miguel Cueto Noval, Ilia Markov, Michelle X Yeo, Joel F Alwen, and Krzysztof Z Pietrzak. “Keep the Dirt: Tainted TreeKEM, Adaptively and Actively Secure Continuous Group Key Agreement.” In <i>2021 IEEE Symposium on Security and Privacy </i>, 268–84. IEEE, 2021. <a href=\"https://doi.org/10.1109/sp40001.2021.00035\">https://doi.org/10.1109/sp40001.2021.00035</a>.","ieee":"K. Klein <i>et al.</i>, “Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement,” in <i>2021 IEEE Symposium on Security and Privacy </i>, San Francisco, CA, United States, 2021, pp. 268–284.","ista":"Klein K, Pascual Perez G, Walter M, Kamath Hosdurg C, Capretto M, Cueto Noval M, Markov I, Yeo MX, Alwen JF, Pietrzak KZ. 2021. Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement. 2021 IEEE Symposium on Security and Privacy . SP: Symposium on Security and Privacy, 268–284.","apa":"Klein, K., Pascual Perez, G., Walter, M., Kamath Hosdurg, C., Capretto, M., Cueto Noval, M., … Pietrzak, K. Z. (2021). Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement. In <i>2021 IEEE Symposium on Security and Privacy </i> (pp. 268–284). San Francisco, CA, United States: IEEE. <a href=\"https://doi.org/10.1109/sp40001.2021.00035\">https://doi.org/10.1109/sp40001.2021.00035</a>","mla":"Klein, Karen, et al. “Keep the Dirt: Tainted TreeKEM, Adaptively and Actively Secure Continuous Group Key Agreement.” <i>2021 IEEE Symposium on Security and Privacy </i>, IEEE, 2021, pp. 268–84, doi:<a href=\"https://doi.org/10.1109/sp40001.2021.00035\">10.1109/sp40001.2021.00035</a>."},"scopus_import":"1","author":[{"first_name":"Karen","last_name":"Klein","full_name":"Klein, Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Pascual Perez","full_name":"Pascual Perez, Guillermo","orcid":"0000-0001-8630-415X","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","first_name":"Guillermo"},{"first_name":"Michael","last_name":"Walter","full_name":"Walter, Michael","orcid":"0000-0003-3186-2482","id":"488F98B0-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","orcid":"0009-0006-6812-7317","full_name":"Kamath Hosdurg, Chethan","last_name":"Kamath Hosdurg"},{"first_name":"Margarita","last_name":"Capretto","full_name":"Capretto, Margarita"},{"first_name":"Miguel","full_name":"Cueto Noval, Miguel","last_name":"Cueto Noval","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","orcid":"0000-0002-2505-4246"},{"last_name":"Markov","full_name":"Markov, Ilia","id":"D0CF4148-C985-11E9-8066-0BDEE5697425","first_name":"Ilia"},{"last_name":"Yeo","full_name":"Yeo, Michelle X","orcid":"0009-0001-3676-4809","id":"2D82B818-F248-11E8-B48F-1D18A9856A87","first_name":"Michelle X"},{"last_name":"Alwen","full_name":"Alwen, Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","first_name":"Joel F"},{"first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","publisher":"IEEE","doi":"10.1109/sp40001.2021.00035","year":"2021","page":"268-284","month":"08","date_published":"2021-08-26T00:00:00Z","day":"26","conference":{"end_date":"2021-05-27","name":"SP: Symposium on Security and Privacy","location":"San Francisco, CA, United States","start_date":"2021-05-24"},"ec_funded":1,"department":[{"_id":"KrPi"},{"_id":"DaAl"}],"external_id":{"isi":["001316065000016"]},"project":[{"call_identifier":"H2020","grant_number":"665385","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","name":"International IST Doctoral Program"},{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020"}],"related_material":{"record":[{"id":"18088","relation":"dissertation_contains","status":"public"},{"status":"public","id":"10035","relation":"dissertation_contains"}]},"oa_version":"Preprint","type":"conference","acknowledgement":"The first three authors contributed equally to this work. Funded by the European Research Council (ERC) under the European Union’s Horizon2020 research and innovation programme (682815-TOCNeT). Funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No.665385.","oa":1,"isi":1,"status":"public","language":[{"iso":"eng"}],"_id":"10049","date_updated":"2026-04-08T07:01:44Z"},{"oa":1,"isi":1,"_id":"10408","date_updated":"2026-04-07T13:01:26Z","language":[{"iso":"eng"}],"status":"public","publication_identifier":{"isbn":["9-783-0309-0455-5"],"issn":["0302-9743"],"eissn":["1611-3349"],"eisbn":["978-3-030-90456-2"]},"related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"18088"}]},"project":[{"call_identifier":"H2020","grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks"},{"call_identifier":"H2020","grant_number":"665385","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","name":"International IST Doctoral Program"}],"external_id":{"isi":["000728363700008"]},"department":[{"_id":"KrPi"}],"ec_funded":1,"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).","oa_version":"Preprint","type":"conference","year":"2021","page":"222-253","month":"11","volume":13044,"publisher":"Springer Nature","doi":"10.1007/978-3-030-90456-2_8","alternative_title":["LNCS"],"date_published":"2021-11-04T00:00:00Z","day":"04","conference":{"name":"TCC: Theory of Cryptography","end_date":"2021-11-11","start_date":"2021-11-08","location":"Raleigh, NC, United States"},"publication":"19th International Conference","quality_controlled":"1","intvolume":"     13044","title":"Grafting key trees: Efficient key management for overlapping groups","scopus_import":"1","author":[{"id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","last_name":"Alwen","full_name":"Alwen, Joel F","first_name":"Joel F"},{"first_name":"Benedikt","last_name":"Auerbach","full_name":"Auerbach, Benedikt","orcid":"0000-0002-7553-6606","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425"},{"first_name":"Mirza Ahad","id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425","full_name":"Baig, Mirza Ahad","last_name":"Baig"},{"first_name":"Miguel","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","orcid":"0000-0002-2505-4246","full_name":"Cueto Noval, Miguel","last_name":"Cueto Noval"},{"last_name":"Klein","full_name":"Klein, Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","first_name":"Karen"},{"first_name":"Guillermo","full_name":"Pascual Perez, Guillermo","last_name":"Pascual Perez","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8630-415X"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","first_name":"Krzysztof Z"},{"first_name":"Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3186-2482","full_name":"Walter, Michael","last_name":"Walter"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","article_processing_charge":"No","date_created":"2021-12-05T23:01:42Z","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2021/1158"}],"publication_status":"published","citation":{"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 <i>19th International Conference</i> (Vol. 13044, pp. 222–253). Raleigh, NC, United States: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-90456-2_8\">https://doi.org/10.1007/978-3-030-90456-2_8</a>","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.","ieee":"J. F. Alwen <i>et al.</i>, “Grafting key trees: Efficient key management for overlapping groups,” in <i>19th International Conference</i>, Raleigh, NC, United States, 2021, vol. 13044, pp. 222–253.","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 <i>19th International Conference</i>, 13044:222–53. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-90456-2_8\">https://doi.org/10.1007/978-3-030-90456-2_8</a>.","ama":"Alwen JF, Auerbach B, Baig MA, et al. Grafting key trees: Efficient key management for overlapping groups. In: <i>19th International Conference</i>. Vol 13044. Springer Nature; 2021:222-253. doi:<a href=\"https://doi.org/10.1007/978-3-030-90456-2_8\">10.1007/978-3-030-90456-2_8</a>","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.","mla":"Alwen, Joel F., et al. “Grafting Key Trees: Efficient Key Management for Overlapping Groups.” <i>19th International Conference</i>, vol. 13044, Springer Nature, 2021, pp. 222–53, doi:<a href=\"https://doi.org/10.1007/978-3-030-90456-2_8\">10.1007/978-3-030-90456-2_8</a>."},"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."}]},{"conference":{"name":"CT-RSA: Cryptographers’ Track at the RSA Conference","end_date":"2021-05-20","start_date":"2021-05-17","location":"Virtual Event"},"date_published":"2021-05-11T00:00:00Z","day":"11","alternative_title":["LNCS"],"doi":"10.1007/978-3-030-75539-3_17","publisher":"Springer Nature","volume":12704,"month":"05","year":"2021","page":"399-421","abstract":[{"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.","lang":"eng"}],"citation":{"ieee":"B. Auerbach <i>et al.</i>, “Inverse-Sybil attacks in automated contact tracing,” in <i>Topics in Cryptology – CT-RSA 2021</i>, Virtual Event, 2021, vol. 12704, pp. 399–421.","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 <i>Topics in Cryptology – CT-RSA 2021</i>, 12704:399–421. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-75539-3_17\">https://doi.org/10.1007/978-3-030-75539-3_17</a>.","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.","apa":"Auerbach, B., Chakraborty, S., Klein, K., Pascual Perez, G., Pietrzak, K. Z., Walter, M., &#38; Yeo, M. X. (2021). Inverse-Sybil attacks in automated contact tracing. In <i>Topics in Cryptology – CT-RSA 2021</i> (Vol. 12704, pp. 399–421). Virtual Event: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-75539-3_17\">https://doi.org/10.1007/978-3-030-75539-3_17</a>","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.","ama":"Auerbach B, Chakraborty S, Klein K, et al. Inverse-Sybil attacks in automated contact tracing. In: <i>Topics in Cryptology – CT-RSA 2021</i>. Vol 12704. Springer Nature; 2021:399-421. doi:<a href=\"https://doi.org/10.1007/978-3-030-75539-3_17\">10.1007/978-3-030-75539-3_17</a>","mla":"Auerbach, Benedikt, et al. “Inverse-Sybil Attacks in Automated Contact Tracing.” <i>Topics in Cryptology – CT-RSA 2021</i>, vol. 12704, Springer Nature, 2021, pp. 399–421, doi:<a href=\"https://doi.org/10.1007/978-3-030-75539-3_17\">10.1007/978-3-030-75539-3_17</a>."},"publication_status":"published","article_processing_charge":"No","date_created":"2021-08-08T22:01:30Z","main_file_link":[{"url":"https://eprint.iacr.org/2020/670","open_access":"1"}],"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","scopus_import":"1","author":[{"last_name":"Auerbach","full_name":"Auerbach, Benedikt","orcid":"0000-0002-7553-6606","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","first_name":"Benedikt"},{"full_name":"Chakraborty, Suvradip","last_name":"Chakraborty","id":"B9CD0494-D033-11E9-B219-A439E6697425","first_name":"Suvradip"},{"full_name":"Klein, Karen","last_name":"Klein","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","first_name":"Karen"},{"first_name":"Guillermo","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8630-415X","full_name":"Pascual Perez, Guillermo","last_name":"Pascual Perez"},{"first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z"},{"first_name":"Michael","full_name":"Walter, Michael","last_name":"Walter","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3186-2482"},{"orcid":"0009-0001-3676-4809","id":"2D82B818-F248-11E8-B48F-1D18A9856A87","last_name":"Yeo","full_name":"Yeo, Michelle X","first_name":"Michelle X"}],"intvolume":"     12704","title":"Inverse-Sybil attacks in automated contact tracing","publication":"Topics in Cryptology – CT-RSA 2021","quality_controlled":"1","corr_author":"1","publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["9783030755386"]},"language":[{"iso":"eng"}],"status":"public","_id":"9826","date_updated":"2026-04-16T09:28:46Z","oa":1,"type":"conference","oa_version":"Submitted Version","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).","department":[{"_id":"KrPi"},{"_id":"GradSch"}],"ec_funded":1,"project":[{"name":"International IST Doctoral Program","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","grant_number":"665385","call_identifier":"H2020"},{"call_identifier":"H2020","grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks"}]}]