[{"article_processing_charge":"No","date_published":"2023-11-27T00:00:00Z","month":"11","date_updated":"2023-12-18T08:36:51Z","title":"On the cost of post-compromise security in concurrent Continuous Group-Key Agreement","date_created":"2023-12-17T23:00:53Z","_id":"14691","page":"271-300","publication":"21st International Conference on Theory of Cryptography","oa":1,"intvolume":"     14371","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"url":"https://eprint.iacr.org/2023/1123","open_access":"1"}],"alternative_title":["LNCS"],"volume":14371,"scopus_import":"1","conference":{"name":"TCC: Theory of Cryptography","end_date":"2023-12-02","location":"Taipei, Taiwan","start_date":"2023-11-29"},"year":"2023","author":[{"last_name":"Auerbach","full_name":"Auerbach, Benedikt","orcid":"0000-0002-7553-6606","first_name":"Benedikt","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425"},{"first_name":"Miguel","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","last_name":"Cueto Noval","full_name":"Cueto Noval, Miguel"},{"full_name":"Pascual Perez, Guillermo","orcid":"0000-0001-8630-415X","last_name":"Pascual Perez","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","first_name":"Guillermo"},{"last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"}],"department":[{"_id":"KrPi"}],"publication_identifier":{"isbn":["9783031486203"],"issn":["0302-9743"],"eissn":["1611-3349"]},"day":"27","publisher":"Springer Nature","oa_version":"Preprint","doi":"10.1007/978-3-031-48621-0_10","quality_controlled":"1","status":"public","language":[{"iso":"eng"}],"publication_status":"published","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"}],"type":"conference","citation":{"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>.","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>","ista":"Auerbach B, Cueto Noval M, Pascual Perez G, Pietrzak KZ. 2023. On the cost of post-compromise security in concurrent Continuous Group-Key Agreement. 21st International Conference on Theory of Cryptography. TCC: Theory of Cryptography, LNCS, vol. 14371, 271–300.","mla":"Auerbach, Benedikt, et al. “On the Cost of Post-Compromise Security in Concurrent Continuous Group-Key Agreement.” <i>21st International Conference on Theory of Cryptography</i>, vol. 14371, Springer Nature, 2023, pp. 271–300, doi:<a href=\"https://doi.org/10.1007/978-3-031-48621-0_10\">10.1007/978-3-031-48621-0_10</a>.","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.","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."}},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"intvolume":"     14371","alternative_title":["LNCS"],"volume":14371,"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2023/808"}],"scopus_import":"1","date_published":"2023-11-27T00:00:00Z","article_processing_charge":"No","month":"11","date_updated":"2023-12-18T09:17:03Z","title":"Generic-group lower bounds via reductions between geometric-search problems: With and without preprocessing","date_created":"2023-12-17T23:00:54Z","_id":"14692","page":"301-330","publication":"21st International Conference on Theory of Cryptography","quality_controlled":"1","language":[{"iso":"eng"}],"status":"public","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."}],"publication_status":"published","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>.","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.","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>.","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>","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.","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>","short":"B. Auerbach, C. Hoffmann, G. Pascual Perez, in:, 21st International Conference on Theory of Cryptography, Springer Nature, 2023, pp. 301–330."},"type":"conference","author":[{"orcid":"0000-0002-7553-6606","full_name":"Auerbach, Benedikt","last_name":"Auerbach","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","first_name":"Benedikt"},{"first_name":"Charlotte","id":"0f78d746-dc7d-11ea-9b2f-83f92091afe7","last_name":"Hoffmann","orcid":"0000-0003-2027-5549","full_name":"Hoffmann, Charlotte"},{"id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","first_name":"Guillermo","last_name":"Pascual Perez","orcid":"0000-0001-8630-415X","full_name":"Pascual Perez, Guillermo"}],"year":"2023","publication_identifier":{"issn":["0302-9743"],"eissn":["1611-3349"],"isbn":["9783031486203"]},"department":[{"_id":"KrPi"}],"day":"27","publisher":"Springer Nature","oa_version":"Preprint","doi":"10.1007/978-3-031-48621-0_11"}]