[{"article_processing_charge":"No","_id":"11476","date_published":"2022-05-25T00:00:00Z","abstract":[{"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.","lang":"eng"}],"publication_status":"published","main_file_link":[{"url":"https://eprint.iacr.org/2022/251","open_access":"1"}],"oa":1,"volume":13276,"year":"2022","oa_version":"Preprint","scopus_import":"1","external_id":{"isi":["000832305300028"]},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","date_updated":"2023-08-03T07:25:02Z","publication_identifier":{"eisbn":["9783031070853"],"isbn":["9783031070846"],"issn":["0302-9743"],"eissn":["1611-3349"]},"page":"815–844","month":"05","place":"Cham","date_created":"2022-06-30T16:48:00Z","publisher":"Springer Nature","isi":1,"publication":"Advances in Cryptology – EUROCRYPT 2022","quality_controlled":"1","department":[{"_id":"GradSch"},{"_id":"KrPi"}],"status":"public","intvolume":"     13276","citation":{"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.","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>","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>","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.","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.","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>.","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>."},"ec_funded":1,"title":"CoCoA: Concurrent continuous group key agreement","conference":{"location":"Trondheim, Norway","name":"EUROCRYPT: Annual International Conference on the Theory and Applications of Cryptology and Information Security","start_date":"2022-05-30","end_date":"2022-06-03"},"day":"25","type":"conference","author":[{"full_name":"Alwen, Joël","first_name":"Joël","last_name":"Alwen"},{"orcid":"0000-0002-7553-6606","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","last_name":"Auerbach","first_name":"Benedikt","full_name":"Auerbach, Benedikt"},{"last_name":"Cueto Noval","full_name":"Cueto Noval, Miguel","first_name":"Miguel","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc"},{"id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","last_name":"Klein","first_name":"Karen","full_name":"Klein, Karen"},{"id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","last_name":"Pascual Perez","first_name":"Guillermo","full_name":"Pascual Perez, Guillermo"},{"last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654"},{"full_name":"Walter, Michael","first_name":"Michael","last_name":"Walter"}],"alternative_title":["LNCS"],"project":[{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","name":"Teaching Old Crypto New Tricks"},{"_id":"2564DBCA-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"International IST Doctoral Program","grant_number":"665385"}],"acknowledgement":"We thank Marta Mularczyk and Yiannis Tselekounis for their very helpful feedback on an earlier draft of this paper.","language":[{"iso":"eng"}],"doi":"10.1007/978-3-031-07085-3_28"},{"language":[{"iso":"eng"}],"ddc":["000"],"doi":"10.1007/978-3-030-75245-3_3","project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"acknowledgement":"This work was initiated in discussions with Léo Ducas, when the author was visiting the Simons Institute for the Theory of Computation during the program “Lattices: Algorithms, Complexity, and Cryptography”. We thank Thomas Espitau for pointing out a bug in a proof in an earlier version of this manuscript.","day":"01","author":[{"first_name":"Michael","full_name":"Walter, Michael","last_name":"Walter","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3186-2482"}],"type":"conference","alternative_title":["LNCS"],"citation":{"mla":"Walter, Michael. “The Convergence of Slide-Type Reductions.” <i>Public-Key Cryptography – PKC 2021</i>, vol. 12710, Springer Nature, 2021, pp. 45–67, doi:<a href=\"https://doi.org/10.1007/978-3-030-75245-3_3\">10.1007/978-3-030-75245-3_3</a>.","chicago":"Walter, Michael. “The Convergence of Slide-Type Reductions.” In <i>Public-Key Cryptography – PKC 2021</i>, 12710:45–67. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-75245-3_3\">https://doi.org/10.1007/978-3-030-75245-3_3</a>.","ieee":"M. Walter, “The convergence of slide-type reductions,” in <i>Public-Key Cryptography – PKC 2021</i>, Virtual, 2021, vol. 12710, pp. 45–67.","ista":"Walter M. 2021. The convergence of slide-type reductions. Public-Key Cryptography – PKC 2021. PKC: IACR International Conference on Practice and Theory of Public Key Cryptography, LNCS, vol. 12710, 45–67.","ama":"Walter M. The convergence of slide-type reductions. In: <i>Public-Key Cryptography – PKC 2021</i>. Vol 12710. Springer Nature; 2021:45-67. doi:<a href=\"https://doi.org/10.1007/978-3-030-75245-3_3\">10.1007/978-3-030-75245-3_3</a>","apa":"Walter, M. (2021). The convergence of slide-type reductions. In <i>Public-Key Cryptography – PKC 2021</i> (Vol. 12710, pp. 45–67). Virtual: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-75245-3_3\">https://doi.org/10.1007/978-3-030-75245-3_3</a>","short":"M. Walter, in:, Public-Key Cryptography – PKC 2021, Springer Nature, 2021, pp. 45–67."},"ec_funded":1,"title":"The convergence of slide-type reductions","conference":{"location":"Virtual","end_date":"2021-05-13","start_date":"2021-05-10","name":"PKC: IACR International Conference on Practice and Theory of Public Key Cryptography"},"publication":"Public-Key Cryptography – PKC 2021","department":[{"_id":"KrPi"}],"quality_controlled":"1","intvolume":"     12710","status":"public","publisher":"Springer Nature","month":"05","date_created":"2021-06-06T22:01:29Z","page":"45-67","scopus_import":"1","date_updated":"2023-02-23T13:58:47Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"issn":["03029743"],"isbn":["9783030752446"],"eissn":["16113349"]},"has_accepted_license":"1","oa_version":"Published Version","year":"2021","file_date_updated":"2022-05-27T09:48:31Z","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"volume":12710,"publication_status":"published","oa":1,"file":[{"file_name":"2021_PKC_Walter.pdf","file_size":489017,"creator":"dernst","checksum":"413e564d645ed93d7318672361d9d470","date_updated":"2022-05-27T09:48:31Z","access_level":"open_access","content_type":"application/pdf","relation":"main_file","file_id":"11416","date_created":"2022-05-27T09:48:31Z","success":1}],"abstract":[{"lang":"eng","text":"In this work, we apply the dynamical systems analysis of Hanrot et al. (CRYPTO’11) to a class of lattice block reduction algorithms that includes (natural variants of) slide reduction and block-Rankin reduction. This implies sharper bounds on the polynomial running times (in the query model) for these algorithms and opens the door to faster practical variants of slide reduction. We give heuristic arguments showing that such variants can indeed speed up slide reduction significantly in practice. This is confirmed by experimental evidence, which also shows that our variants are competitive with state-of-the-art reduction algorithms."}],"_id":"9466","date_published":"2021-05-01T00:00:00Z","article_processing_charge":"No"},{"oa_version":"Published Version","year":"2021","has_accepted_license":"1","date_updated":"2023-10-17T09:24:07Z","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publication_identifier":{"issn":["2663-337X"]},"file":[{"date_created":"2021-10-04T12:22:33Z","success":1,"relation":"main_file","file_id":"10082","content_type":"application/pdf","checksum":"73a44345c683e81f3e765efbf86fdcc5","access_level":"open_access","date_updated":"2021-10-04T12:22:33Z","file_size":2104726,"creator":"cchlebak","file_name":"thesis_pdfa.pdf"},{"file_name":"thesis_final (1).zip","file_size":9538359,"creator":"cchlebak","checksum":"7b80df30a0e686c3ef6a56d4e1c59e29","date_updated":"2022-03-10T12:15:18Z","access_level":"closed","content_type":"application/x-zip-compressed","file_id":"10085","relation":"source_file","date_created":"2021-10-05T07:04:37Z"}],"_id":"10035","date_published":"2021-09-23T00:00:00Z","abstract":[{"text":"Many security definitions come in two flavors: a stronger “adaptive” flavor, where the adversary can arbitrarily make various choices during the course of the attack, and a weaker “selective” flavor where the adversary must commit to some or all of their choices a-priori. For example, in the context of identity-based encryption, selective security requires the adversary to decide on the identity of the attacked party at the very beginning of the game whereas adaptive security allows the attacker to first see the master public key and some secret keys before making this choice. Often, it appears to be much easier to achieve selective security than it is to achieve adaptive security. A series of several recent works shows how to cleverly achieve adaptive security in several such scenarios including generalized selective decryption [Pan07][FJP15], constrained PRFs [FKPR14], and Yao’s garbled circuits [JW16]. Although the above works expressed vague intuition that they share a common technique, the connection was never made precise. In this work we present a new framework (published at Crypto ’17 [JKK+17a]) that connects all of these works and allows us to present them in a unified and simplified fashion. Having the framework in place, we show how to achieve adaptive security for proxy re-encryption schemes (published at PKC ’19 [FKKP19]) and provide the first adaptive security proofs for continuous group key agreement protocols (published at S&P ’21 [KPW+21]). Questioning optimality of our framework, we then show that currently used proof techniques cannot lead to significantly better security guarantees for \"graph-building\" games (published at TCC ’21 [KKPW21a]). These games cover generalized selective decryption, as well as the security of prominent constructions for constrained PRFs, continuous group key agreement, and proxy re-encryption. Finally, we revisit the adaptive security of Yao’s garbled circuits and extend the analysis of Jafargholi and Wichs in two directions: While they prove adaptive security only for a modified construction with increased online complexity, we provide the first positive results for the original construction by Yao (published at TCC ’21 [KKP21a]). On the negative side, we prove that the results of Jafargholi and Wichs are essentially optimal by showing that no black-box reduction can provide a significantly better security bound (published at Crypto ’21 [KKPW21c]).","lang":"eng"}],"article_processing_charge":"No","file_date_updated":"2022-03-10T12:15:18Z","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"publication_status":"published","oa":1,"day":"23","alternative_title":["ISTA Thesis"],"author":[{"last_name":"Klein","first_name":"Karen","full_name":"Klein, Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87"}],"type":"dissertation","ec_funded":1,"citation":{"mla":"Klein, Karen. <i>On the Adaptive Security of Graph-Based Games</i>. Institute of Science and Technology Austria, 2021, doi:<a href=\"https://doi.org/10.15479/at:ista:10035\">10.15479/at:ista:10035</a>.","ieee":"K. Klein, “On the adaptive security of graph-based games,” Institute of Science and Technology Austria, 2021.","ista":"Klein K. 2021. On the adaptive security of graph-based games. Institute of Science and Technology Austria.","chicago":"Klein, Karen. “On the Adaptive Security of Graph-Based Games.” Institute of Science and Technology Austria, 2021. <a href=\"https://doi.org/10.15479/at:ista:10035\">https://doi.org/10.15479/at:ista:10035</a>.","apa":"Klein, K. (2021). <i>On the adaptive security of graph-based games</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/at:ista:10035\">https://doi.org/10.15479/at:ista:10035</a>","ama":"Klein K. On the adaptive security of graph-based games. 2021. doi:<a href=\"https://doi.org/10.15479/at:ista:10035\">10.15479/at:ista:10035</a>","short":"K. Klein, On the Adaptive Security of Graph-Based Games, Institute of Science and Technology Austria, 2021."},"title":"On the adaptive security of graph-based games","language":[{"iso":"eng"}],"doi":"10.15479/at:ista:10035","ddc":["519"],"acknowledgement":"I want to acknowledge the funding by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT).\r\n","related_material":{"record":[{"id":"10044","relation":"part_of_dissertation","status":"public"},{"id":"10049","relation":"part_of_dissertation","status":"public"},{"status":"public","id":"637","relation":"part_of_dissertation"},{"status":"public","id":"10041","relation":"part_of_dissertation"},{"relation":"part_of_dissertation","id":"6430","status":"public"},{"status":"public","relation":"part_of_dissertation","id":"10048"}]},"project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Teaching Old Crypto New Tricks","grant_number":"682815"}],"month":"09","date_created":"2021-09-23T07:31:44Z","supervisor":[{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z"}],"page":"276","department":[{"_id":"GradSch"},{"_id":"KrPi"}],"status":"public","publisher":"Institute of Science and Technology Austria","degree_awarded":"PhD"},{"doi":"10.1007/978-3-030-84245-1_17","language":[{"iso":"eng"}],"related_material":{"record":[{"id":"10035","relation":"dissertation_contains","status":"public"}]},"project":[{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","grant_number":"682815"}],"acknowledgement":"We would like to thank the anonymous reviewers of Crypto’21 whose detailed comments helped us considerably improve the presentation of the paper.","type":"conference","author":[{"id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","full_name":"Kamath Hosdurg, Chethan","first_name":"Chethan","last_name":"Kamath Hosdurg"},{"id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","full_name":"Klein, Karen","first_name":"Karen","last_name":"Klein"},{"orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z"},{"last_name":"Wichs","first_name":"Daniel","full_name":"Wichs, Daniel"}],"alternative_title":["LCNS"],"day":"11","title":"Limits on the Adaptive Security of Yao’s Garbling","conference":{"start_date":"2021-08-16","end_date":"2021-08-20","name":"CRYPTO: Annual International Cryptology Conference","location":"Virtual"},"citation":{"mla":"Kamath Hosdurg, Chethan, et al. “Limits on the Adaptive Security of Yao’s Garbling.” <i>41st Annual International Cryptology Conference, Part II </i>, vol. 12826, Springer Nature, 2021, pp. 486–515, doi:<a href=\"https://doi.org/10.1007/978-3-030-84245-1_17\">10.1007/978-3-030-84245-1_17</a>.","chicago":"Kamath Hosdurg, Chethan, Karen Klein, Krzysztof Z Pietrzak, and Daniel Wichs. “Limits on the Adaptive Security of Yao’s Garbling.” In <i>41st Annual International Cryptology Conference, Part II </i>, 12826:486–515. Cham: Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-84245-1_17\">https://doi.org/10.1007/978-3-030-84245-1_17</a>.","ista":"Kamath Hosdurg C, Klein K, Pietrzak KZ, Wichs D. 2021. Limits on the Adaptive Security of Yao’s Garbling. 41st Annual International Cryptology Conference, Part II . CRYPTO: Annual International Cryptology Conference, LCNS, vol. 12826, 486–515.","ieee":"C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and D. Wichs, “Limits on the Adaptive Security of Yao’s Garbling,” in <i>41st Annual International Cryptology Conference, Part II </i>, Virtual, 2021, vol. 12826, pp. 486–515.","ama":"Kamath Hosdurg C, Klein K, Pietrzak KZ, Wichs D. Limits on the Adaptive Security of Yao’s Garbling. In: <i>41st Annual International Cryptology Conference, Part II </i>. Vol 12826. Cham: Springer Nature; 2021:486-515. doi:<a href=\"https://doi.org/10.1007/978-3-030-84245-1_17\">10.1007/978-3-030-84245-1_17</a>","apa":"Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., &#38; Wichs, D. (2021). Limits on the Adaptive Security of Yao’s Garbling. In <i>41st Annual International Cryptology Conference, Part II </i> (Vol. 12826, pp. 486–515). Cham: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-84245-1_17\">https://doi.org/10.1007/978-3-030-84245-1_17</a>","short":"C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, D. Wichs, in:, 41st Annual International Cryptology Conference, Part II , Springer Nature, Cham, 2021, pp. 486–515."},"ec_funded":1,"intvolume":"     12826","status":"public","publication":"41st Annual International Cryptology Conference, Part II ","quality_controlled":"1","department":[{"_id":"KrPi"}],"publisher":"Springer Nature","date_created":"2021-09-23T14:06:15Z","month":"08","place":"Cham","page":"486-515","publication_identifier":{"eisbn":["978-3-030-84245-1"],"eissn":["1611-3349"],"isbn":["978-3-030-84244-4"],"issn":["0302-9743"]},"date_updated":"2023-09-07T13:32:11Z","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","year":"2021","oa_version":"Preprint","volume":12826,"oa":1,"main_file_link":[{"url":"https://eprint.iacr.org/2021/945","open_access":"1"}],"publication_status":"published","_id":"10041","date_published":"2021-08-11T00:00:00Z","abstract":[{"text":"Yao’s garbling scheme is one of the most fundamental cryptographic constructions. Lindell and Pinkas (Journal of Cryptograhy 2009) gave a formal proof of security in the selective setting where the adversary chooses the challenge inputs before seeing the garbled circuit assuming secure symmetric-key encryption (and hence one-way functions). This was followed by results, both positive and negative, concerning its security in the, stronger, adaptive setting. Applebaum et al. (Crypto 2013) showed that it cannot satisfy adaptive security as is, due to a simple incompressibility argument. Jafargholi and Wichs (TCC 2017) considered a natural adaptation of Yao’s scheme (where the output mapping is sent in the online phase, together with the garbled input) that circumvents this negative result, and proved that it is adaptively secure, at least for shallow circuits. In particular, they showed that for the class of circuits of depth   δ , the loss in security is at most exponential in   δ . The above results all concern the simulation-based notion of security. In this work, we show that the upper bound of Jafargholi and Wichs is basically optimal in a strong sense. As our main result, we show that there exists a family of Boolean circuits, one for each depth  δ∈N , such that any black-box reduction proving the adaptive indistinguishability of the natural adaptation of Yao’s scheme from any symmetric-key encryption has to lose a factor that is exponential in   δ√ . Since indistinguishability is a weaker notion than simulation, our bound also applies to adaptive simulation. To establish our results, we build on the recent approach of Kamath et al. (Eprint 2021), which uses pebbling lower bounds in conjunction with oracle separations to prove fine-grained lower bounds on loss in cryptographic security.","lang":"eng"}],"article_processing_charge":"No"},{"title":"On treewidth, separators and Yao's garbling","conference":{"name":"TCC: Theory of Cryptography Conference","start_date":"2021-11-08","end_date":"2021-11-11","location":"Raleigh, NC, United States"},"citation":{"short":"C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, in:, 19th Theory of Cryptography Conference 2021, International Association for Cryptologic Research, 2021.","ama":"Kamath Hosdurg C, Klein K, Pietrzak KZ. On treewidth, separators and Yao’s garbling. In: <i>19th Theory of Cryptography Conference 2021</i>. International Association for Cryptologic Research; 2021.","apa":"Kamath Hosdurg, C., Klein, K., &#38; Pietrzak, K. Z. (2021). On treewidth, separators and Yao’s garbling. In <i>19th Theory of Cryptography Conference 2021</i>. Raleigh, NC, United States: International Association for Cryptologic Research.","chicago":"Kamath Hosdurg, Chethan, Karen Klein, and Krzysztof Z Pietrzak. “On Treewidth, Separators and Yao’s Garbling.” In <i>19th Theory of Cryptography Conference 2021</i>. International Association for Cryptologic Research, 2021.","ista":"Kamath Hosdurg C, Klein K, Pietrzak KZ. 2021. On treewidth, separators and Yao’s garbling. 19th Theory of Cryptography Conference 2021. TCC: Theory of Cryptography Conference, 2021/926.","ieee":"C. Kamath Hosdurg, K. Klein, and K. Z. Pietrzak, “On treewidth, separators and Yao’s garbling,” in <i>19th Theory of Cryptography Conference 2021</i>, Raleigh, NC, United States, 2021.","mla":"Kamath Hosdurg, Chethan, et al. “On Treewidth, Separators and Yao’s Garbling.” <i>19th Theory of Cryptography Conference 2021</i>, 2021/926, International Association for Cryptologic Research, 2021."},"ec_funded":1,"type":"conference","author":[{"id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","last_name":"Kamath Hosdurg","full_name":"Kamath Hosdurg, Chethan","first_name":"Chethan"},{"last_name":"Klein","first_name":"Karen","full_name":"Klein, Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak"}],"year":"2021","oa_version":"Preprint","day":"08","project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"related_material":{"record":[{"status":"public","id":"10409","relation":"later_version"},{"status":"public","relation":"dissertation_contains","id":"10035"}]},"acknowledgement":"We would like to thank Daniel Wichs for helpful discussions on the landscape of adaptive security of Yao’s garbling.  ","date_updated":"2023-09-07T13:32:11Z","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","language":[{"iso":"eng"}],"article_processing_charge":"No","date_created":"2021-09-24T12:01:34Z","_id":"10044","date_published":"2021-07-08T00:00:00Z","abstract":[{"lang":"eng","text":"We show that Yao’s garbling scheme is adaptively indistinguishable for the class of Boolean circuits of size S and treewidth w with only a S^O(w) loss in security. For instance, circuits with constant treewidth are as a result adaptively indistinguishable with only a polynomial loss. This (partially) complements a negative result of Applebaum et al. (Crypto 2013), which showed (assuming one-way functions) that Yao’s garbling scheme cannot be adaptively simulatable. As main technical contributions, we introduce a new pebble game that abstracts out our security reduction and then present a pebbling strategy for this game where the number of pebbles used is roughly O(d w log(S)), d being the fan-out of the circuit. The design of the strategy relies on separators, a graph-theoretic notion with connections to circuit complexity."}],"month":"07","article_number":"2021/926","oa":1,"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2021/926"}],"publication_status":"published","publisher":"International Association for Cryptologic Research","status":"public","publication":"19th Theory of Cryptography Conference 2021","department":[{"_id":"KrPi"}],"quality_controlled":"1"},{"year":"2021","oa_version":"Preprint","date_updated":"2023-09-07T13:32:11Z","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","date_published":"2021-08-26T00:00:00Z","_id":"10049","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."}],"article_processing_charge":"No","publication_status":"published","main_file_link":[{"url":"https://eprint.iacr.org/2019/1489","open_access":"1"}],"oa":1,"day":"26","type":"conference","author":[{"last_name":"Klein","full_name":"Klein, Karen","first_name":"Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Pascual Perez","full_name":"Pascual Perez, Guillermo","first_name":"Guillermo","orcid":"0000-0001-8630-415X","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Walter","full_name":"Walter, Michael","first_name":"Michael","orcid":"0000-0003-3186-2482","id":"488F98B0-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Kamath Hosdurg","full_name":"Kamath Hosdurg, Chethan","first_name":"Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Capretto","full_name":"Capretto, Margarita","first_name":"Margarita"},{"id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","last_name":"Cueto Noval","first_name":"Miguel","full_name":"Cueto Noval, Miguel"},{"first_name":"Ilia","full_name":"Markov, Ilia","last_name":"Markov","id":"D0CF4148-C985-11E9-8066-0BDEE5697425"},{"id":"2D82B818-F248-11E8-B48F-1D18A9856A87","last_name":"Yeo","full_name":"Yeo, Michelle X","first_name":"Michelle X"},{"id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","full_name":"Alwen, Joel F","first_name":"Joel F","last_name":"Alwen"},{"full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654"}],"ec_funded":1,"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.","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>","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>","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.","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.","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>.","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>."},"conference":{"location":"San Francisco, CA, United States","name":"SP: Symposium on Security and Privacy","start_date":"2021-05-24","end_date":"2021-05-27"},"title":"Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement","language":[{"iso":"eng"}],"doi":"10.1109/sp40001.2021.00035","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.","project":[{"name":"International IST Doctoral Program","grant_number":"665385","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"},{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"related_material":{"record":[{"id":"10035","relation":"dissertation_contains","status":"public"}]},"month":"08","date_created":"2021-09-27T13:46:27Z","page":"268-284","quality_controlled":"1","department":[{"_id":"KrPi"},{"_id":"DaAl"}],"publication":"2021 IEEE Symposium on Security and Privacy ","status":"public","publisher":"IEEE"},{"department":[{"_id":"KrPi"}],"quality_controlled":"1","status":"public","intvolume":"     13043","publisher":"Springer Nature","isi":1,"month":"11","date_created":"2021-12-05T23:01:42Z","page":"397-428","language":[{"iso":"eng"}],"doi":"10.1007/978-3-030-90453-1_14","project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"day":"04","alternative_title":["LNCS"],"type":"conference","author":[{"last_name":"Chakraborty","full_name":"Chakraborty, Suvradip","first_name":"Suvradip","id":"B9CD0494-D033-11E9-B219-A439E6697425"},{"last_name":"Dziembowski","first_name":"Stefan","full_name":"Dziembowski, Stefan"},{"last_name":"Gałązka","first_name":"Małgorzata","full_name":"Gałązka, Małgorzata"},{"last_name":"Lizurej","full_name":"Lizurej, Tomasz","first_name":"Tomasz"},{"full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Michelle X","full_name":"Yeo, Michelle X","last_name":"Yeo","id":"2D82B818-F248-11E8-B48F-1D18A9856A87"}],"ec_funded":1,"citation":{"apa":"Chakraborty, S., Dziembowski, S., Gałązka, M., Lizurej, T., Pietrzak, K. Z., &#38; Yeo, M. X. (2021). Trojan-resilience without cryptography (Vol. 13043, pp. 397–428). Presented at the TCC: Theory of Cryptography Conference, Raleigh, NC, United States: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-90453-1_14\">https://doi.org/10.1007/978-3-030-90453-1_14</a>","ama":"Chakraborty S, Dziembowski S, Gałązka M, Lizurej T, Pietrzak KZ, Yeo MX. Trojan-resilience without cryptography. In: Vol 13043. Springer Nature; 2021:397-428. doi:<a href=\"https://doi.org/10.1007/978-3-030-90453-1_14\">10.1007/978-3-030-90453-1_14</a>","short":"S. Chakraborty, S. Dziembowski, M. Gałązka, T. Lizurej, K.Z. Pietrzak, M.X. Yeo, in:, Springer Nature, 2021, pp. 397–428.","mla":"Chakraborty, Suvradip, et al. <i>Trojan-Resilience without Cryptography</i>. Vol. 13043, Springer Nature, 2021, pp. 397–428, doi:<a href=\"https://doi.org/10.1007/978-3-030-90453-1_14\">10.1007/978-3-030-90453-1_14</a>.","ista":"Chakraborty S, Dziembowski S, Gałązka M, Lizurej T, Pietrzak KZ, Yeo MX. 2021. Trojan-resilience without cryptography. TCC: Theory of Cryptography Conference, LNCS, vol. 13043, 397–428.","ieee":"S. Chakraborty, S. Dziembowski, M. Gałązka, T. Lizurej, K. Z. Pietrzak, and M. X. Yeo, “Trojan-resilience without cryptography,” presented at the TCC: Theory of Cryptography Conference, Raleigh, NC, United States, 2021, vol. 13043, pp. 397–428.","chicago":"Chakraborty, Suvradip, Stefan Dziembowski, Małgorzata Gałązka, Tomasz Lizurej, Krzysztof Z Pietrzak, and Michelle X Yeo. “Trojan-Resilience without Cryptography,” 13043:397–428. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-90453-1_14\">https://doi.org/10.1007/978-3-030-90453-1_14</a>."},"conference":{"location":"Raleigh, NC, United States","name":"TCC: Theory of Cryptography Conference","start_date":"2021-11-08","end_date":"2021-11-11"},"title":"Trojan-resilience without cryptography","volume":13043,"publication_status":"published","oa":1,"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2021/1224"}],"abstract":[{"text":"Digital hardware Trojans are integrated circuits whose implementation differ from the specification in an arbitrary and malicious way. For example, the circuit can differ from its specified input/output behavior after some fixed number of queries (known as “time bombs”) or on some particular input (known as “cheat codes”). To detect such Trojans, countermeasures using multiparty computation (MPC) or verifiable computation (VC) have been proposed. On a high level, to realize a circuit with specification   F  one has more sophisticated circuits   F⋄  manufactured (where   F⋄  specifies a MPC or VC of   F ), and then embeds these   F⋄ ’s into a master circuit which must be trusted but is relatively simple compared to   F . Those solutions impose a significant overhead as   F⋄  is much more complex than   F , also the master circuits are not exactly trivial. In this work, we show that in restricted settings, where   F  has no evolving state and is queried on independent inputs, we can achieve a relaxed security notion using very simple constructions. In particular, we do not change the specification of the circuit at all (i.e.,   F=F⋄ ). Moreover the master circuit basically just queries a subset of its manufactured circuits and checks if they’re all the same. The security we achieve guarantees that, if the manufactured circuits are initially tested on up to T inputs, the master circuit will catch Trojans that try to deviate on significantly more than a 1/T fraction of the inputs. This bound is optimal for the type of construction considered, and we provably achieve it using a construction where 12 instantiations of   F  need to be embedded into the master. We also discuss an extremely simple construction with just 2 instantiations for which we conjecture that it already achieves the optimal bound.","lang":"eng"}],"_id":"10407","date_published":"2021-11-04T00:00:00Z","article_processing_charge":"No","date_updated":"2023-08-14T13:07:46Z","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","external_id":{"isi":["000728364000014"]},"scopus_import":"1","publication_identifier":{"eissn":["1611-3349"],"isbn":["9-783-0309-0452-4"],"issn":["0302-9743"]},"oa_version":"Preprint","year":"2021"},{"abstract":[{"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.","lang":"eng"}],"_id":"10408","date_published":"2021-11-04T00:00:00Z","article_processing_charge":"No","volume":13044,"oa":1,"main_file_link":[{"url":"https://eprint.iacr.org/2021/1158","open_access":"1"}],"publication_status":"published","oa_version":"Preprint","year":"2021","publication_identifier":{"isbn":["9-783-0309-0455-5"],"issn":["0302-9743"],"eissn":["1611-3349"],"eisbn":["978-3-030-90456-2"]},"external_id":{"isi":["000728363700008"]},"scopus_import":"1","date_updated":"2023-08-14T13:19:39Z","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","date_created":"2021-12-05T23:01:42Z","month":"11","page":"222-253","status":"public","intvolume":"     13044","publication":"19th International Conference","department":[{"_id":"KrPi"}],"quality_controlled":"1","isi":1,"publisher":"Springer Nature","author":[{"id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","last_name":"Alwen","full_name":"Alwen, Joel F","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":"Mirza Ahad","full_name":"Baig, Mirza Ahad","last_name":"Baig","id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425"},{"id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","full_name":"Cueto Noval, Miguel","first_name":"Miguel","last_name":"Cueto Noval"},{"id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","last_name":"Klein","full_name":"Klein, Karen","first_name":"Karen"},{"id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8630-415X","full_name":"Pascual Perez, Guillermo","first_name":"Guillermo","last_name":"Pascual Perez"},{"orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","last_name":"Pietrzak"},{"full_name":"Walter, Michael","first_name":"Michael","last_name":"Walter","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3186-2482"}],"type":"conference","alternative_title":["LNCS"],"day":"04","title":"Grafting key trees: Efficient key management for overlapping groups","conference":{"end_date":"2021-11-11","start_date":"2021-11-08","name":"TCC: Theory of Cryptography","location":"Raleigh, NC, United States"},"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>","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>.","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.","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.","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>."},"ec_funded":1,"doi":"10.1007/978-3-030-90456-2_8","language":[{"iso":"eng"}],"project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"},{"grant_number":"665385","name":"International IST Doctoral Program","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"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)."},{"project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Teaching Old Crypto New Tricks","grant_number":"682815"}],"related_material":{"record":[{"status":"public","id":"10044","relation":"earlier_version"}]},"acknowledgement":"We are grateful to Daniel Wichs for helpful discussions on the landscape of adaptive security of Yao’s garbling. We would also like to thank Crypto 2021 and TCC 2021 reviewers for their detailed review and suggestions, which helped improve presentation considerably.","doi":"10.1007/978-3-030-90453-1_17","language":[{"iso":"eng"}],"title":"On treewidth, separators and Yao’s garbling","conference":{"location":"Raleigh, NC, United States","name":"TCC: Theory of Cryptography","end_date":"2021-11-11","start_date":"2021-11-08"},"citation":{"short":"C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, in:, 19th International Conference, Springer Nature, 2021, pp. 486–517.","apa":"Kamath Hosdurg, C., Klein, K., &#38; Pietrzak, K. Z. (2021). On treewidth, separators and Yao’s garbling. In <i>19th International Conference</i> (Vol. 13043, pp. 486–517). Raleigh, NC, United States: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-90453-1_17\">https://doi.org/10.1007/978-3-030-90453-1_17</a>","ama":"Kamath Hosdurg C, Klein K, Pietrzak KZ. On treewidth, separators and Yao’s garbling. In: <i>19th International Conference</i>. Vol 13043. Springer Nature; 2021:486-517. doi:<a href=\"https://doi.org/10.1007/978-3-030-90453-1_17\">10.1007/978-3-030-90453-1_17</a>","ieee":"C. Kamath Hosdurg, K. Klein, and K. Z. Pietrzak, “On treewidth, separators and Yao’s garbling,” in <i>19th International Conference</i>, Raleigh, NC, United States, 2021, vol. 13043, pp. 486–517.","ista":"Kamath Hosdurg C, Klein K, Pietrzak KZ. 2021. On treewidth, separators and Yao’s garbling. 19th International Conference. TCC: Theory of Cryptography, LNCS, vol. 13043, 486–517.","chicago":"Kamath Hosdurg, Chethan, Karen Klein, and Krzysztof Z Pietrzak. “On Treewidth, Separators and Yao’s Garbling.” In <i>19th International Conference</i>, 13043:486–517. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-90453-1_17\">https://doi.org/10.1007/978-3-030-90453-1_17</a>.","mla":"Kamath Hosdurg, Chethan, et al. “On Treewidth, Separators and Yao’s Garbling.” <i>19th International Conference</i>, vol. 13043, Springer Nature, 2021, pp. 486–517, doi:<a href=\"https://doi.org/10.1007/978-3-030-90453-1_17\">10.1007/978-3-030-90453-1_17</a>."},"ec_funded":1,"author":[{"id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","last_name":"Kamath Hosdurg","full_name":"Kamath Hosdurg, Chethan","first_name":"Chethan"},{"id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","last_name":"Klein","first_name":"Karen","full_name":"Klein, Karen"},{"last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654"}],"type":"conference","alternative_title":["LNCS"],"day":"04","isi":1,"publisher":"Springer Nature","status":"public","publication":"19th International Conference","department":[{"_id":"KrPi"}],"quality_controlled":"1","page":"486-517","date_created":"2021-12-05T23:01:43Z","month":"11","publication_identifier":{"issn":["0302-9743"],"isbn":["9-783-0309-0452-4"],"eissn":["1611-3349"]},"external_id":{"isi":["000728364000017"]},"scopus_import":"1","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","date_updated":"2023-08-17T06:21:38Z","year":"2021","oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2021/926"}],"oa":1,"publication_status":"published","volume":"13043 ","article_processing_charge":"No","date_published":"2021-11-04T00:00:00Z","_id":"10409","abstract":[{"text":"We show that Yao’s garbling scheme is adaptively indistinguishable for the class of Boolean circuits of size   S  and treewidth   w  with only a   SO(w)  loss in security. For instance, circuits with constant treewidth are as a result adaptively indistinguishable with only a polynomial loss. This (partially) complements a negative result of Applebaum et al. (Crypto 2013), which showed (assuming one-way functions) that Yao’s garbling scheme cannot be adaptively simulatable. As main technical contributions, we introduce a new pebble game that abstracts out our security reduction and then present a pebbling strategy for this game where the number of pebbles used is roughly   O(δwlog(S)) ,   δ  being the fan-out of the circuit. The design of the strategy relies on separators, a graph-theoretic notion with connections to circuit complexity.  with only a   SO(w)  loss in security. For instance, circuits with constant treewidth are as a result adaptively indistinguishable with only a polynomial loss. This (partially) complements a negative result of Applebaum et al. (Crypto 2013), which showed (assuming one-way functions) that Yao’s garbling scheme cannot be adaptively simulatable. As main technical contributions, we introduce a new pebble game that abstracts out our security reduction and then present a pebbling strategy for this game where the number of pebbles used is roughly   O(δwlog(S)) ,   δ  being the fan-out of the circuit. The design of the strategy relies on separators, a graph-theoretic notion with connections to circuit complexity.","lang":"eng"}]},{"volume":13043,"publication_status":"published","oa":1,"main_file_link":[{"open_access":"1","url":"https://ia.cr/2021/059"}],"abstract":[{"lang":"eng","text":"The security of cryptographic primitives and protocols against adversaries that are allowed to make adaptive choices (e.g., which parties to corrupt or which queries to make) is notoriously difficult to establish. A broad theoretical framework was introduced by Jafargholi et al. [Crypto’17] for this purpose. In this paper we initiate the study of lower bounds on loss in adaptive security for certain cryptographic protocols considered in the framework. We prove lower bounds that almost match the upper bounds (proven using the framework) for proxy re-encryption, prefix-constrained PRFs and generalized selective decryption, a security game that captures the security of certain group messaging and broadcast encryption schemes. Those primitives have in common that their security game involves an underlying graph that can be adaptively built by the adversary. Some of our lower bounds only apply to a restricted class of black-box reductions which we term “oblivious” (the existing upper bounds are of this restricted type), some apply to the broader but still restricted class of non-rewinding reductions, while our lower bound for proxy re-encryption applies to all black-box reductions. The fact that some of our lower bounds seem to crucially rely on obliviousness or at least a non-rewinding reduction hints to the exciting possibility that the existing upper bounds can be improved by using more sophisticated reductions. Our main conceptual contribution is a two-player multi-stage game called the Builder-Pebbler Game. We can translate bounds on the winning probabilities for various instantiations of this game into cryptographic lower bounds for the above-mentioned primitives using oracle separation techniques."}],"_id":"10410","date_published":"2021-11-04T00:00:00Z","article_processing_charge":"No","date_updated":"2023-10-17T09:24:07Z","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","scopus_import":"1","external_id":{"isi":["000728364000019"]},"publication_identifier":{"issn":["0302-9743"],"isbn":["9-783-0309-0452-4"],"eissn":["1611-3349"]},"oa_version":"Preprint","year":"2021","department":[{"_id":"KrPi"}],"quality_controlled":"1","publication":"19th International Conference","status":"public","intvolume":"     13043","publisher":"Springer Nature","isi":1,"month":"11","date_created":"2021-12-05T23:01:43Z","page":"550-581","language":[{"iso":"eng"}],"doi":"10.1007/978-3-030-90453-1_19","acknowledgement":"C. Kamath—Supported by Azrieli International Postdoctoral Fellowship. Most of the work was done while the author was at Northeastern University and Charles University, funded by the IARPA grant IARPA/2019-19-020700009 and project PRIMUS/17/SCI/9, respectively. K. Klein—Supported in part by ERC CoG grant 724307. Most of the work was done while the author was at IST Austria funded by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT). K. Pietrzak—Funded by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT).","project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"related_material":{"record":[{"id":"10048","relation":"earlier_version","status":"public"}]},"day":"04","alternative_title":["LNCS"],"type":"conference","author":[{"id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","last_name":"Kamath Hosdurg","full_name":"Kamath Hosdurg, Chethan","first_name":"Chethan"},{"first_name":"Karen","full_name":"Klein, Karen","last_name":"Klein","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","last_name":"Pietrzak"},{"full_name":"Walter, Michael","first_name":"Michael","last_name":"Walter","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3186-2482"}],"ec_funded":1,"citation":{"mla":"Kamath Hosdurg, Chethan, et al. “The Cost of Adaptivity in Security Games on Graphs.” <i>19th International Conference</i>, vol. 13043, Springer Nature, 2021, pp. 550–81, doi:<a href=\"https://doi.org/10.1007/978-3-030-90453-1_19\">10.1007/978-3-030-90453-1_19</a>.","ista":"Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. 2021. The cost of adaptivity in security games on graphs. 19th International Conference. TCC: Theory of Cryptography, LNCS, vol. 13043, 550–581.","ieee":"C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and M. Walter, “The cost of adaptivity in security games on graphs,” in <i>19th International Conference</i>, Raleigh, NC, United States, 2021, vol. 13043, pp. 550–581.","chicago":"Kamath Hosdurg, Chethan, Karen Klein, Krzysztof Z Pietrzak, and Michael Walter. “The Cost of Adaptivity in Security Games on Graphs.” In <i>19th International Conference</i>, 13043:550–81. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-90453-1_19\">https://doi.org/10.1007/978-3-030-90453-1_19</a>.","apa":"Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., &#38; Walter, M. (2021). The cost of adaptivity in security games on graphs. In <i>19th International Conference</i> (Vol. 13043, pp. 550–581). Raleigh, NC, United States: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-90453-1_19\">https://doi.org/10.1007/978-3-030-90453-1_19</a>","ama":"Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. The cost of adaptivity in security games on graphs. In: <i>19th International Conference</i>. Vol 13043. Springer Nature; 2021:550-581. doi:<a href=\"https://doi.org/10.1007/978-3-030-90453-1_19\">10.1007/978-3-030-90453-1_19</a>","short":"C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, M. Walter, in:, 19th International Conference, Springer Nature, 2021, pp. 550–581."},"conference":{"start_date":"2021-11-08","end_date":"2021-11-11","name":"TCC: Theory of Cryptography","location":"Raleigh, NC, United States"},"title":"The cost of adaptivity in security games on graphs"},{"date_updated":"2023-08-17T06:34:41Z","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","external_id":{"isi":["000927876200012"]},"scopus_import":"1","publication_identifier":{"isbn":["978-3-030-92074-6"],"issn":["0302-9743"],"eissn":["1611-3349"],"eisbn":["978-3-030-92075-3"]},"year":"2021","oa_version":"Preprint","volume":13091,"publication_status":"published","oa":1,"main_file_link":[{"url":"https://eprint.iacr.org/2021/1262","open_access":"1"}],"_id":"10609","abstract":[{"text":"We study Multi-party computation (MPC) in the setting of subversion, where the adversary tampers with the machines of honest parties. Our goal is to construct actively secure MPC protocols where parties are corrupted adaptively by an adversary (as in the standard adaptive security setting), and in addition, honest parties’ machines are compromised.\r\nThe idea of reverse firewalls (RF) was introduced at EUROCRYPT’15 by Mironov and Stephens-Davidowitz as an approach to protecting protocols against corruption of honest parties’ devices. Intuitively, an RF for a party   P  is an external entity that sits between   P  and the outside world and whose scope is to sanitize   P ’s incoming and outgoing messages in the face of subversion of their computer. Mironov and Stephens-Davidowitz constructed a protocol for passively-secure two-party computation. At CRYPTO’20, Chakraborty, Dziembowski and Nielsen constructed a protocol for secure computation with firewalls that improved on this result, both by extending it to multi-party computation protocol, and considering active security in the presence of static corruptions. In this paper, we initiate the study of RF for MPC in the adaptive setting. We put forward a definition for adaptively secure MPC in the reverse firewall setting, explore relationships among the security notions, and then construct reverse firewalls for MPC in this stronger setting of adaptive security. We also resolve the open question of Chakraborty, Dziembowski and Nielsen by removing the need for a trusted setup in constructing RF for MPC. Towards this end, we construct reverse firewalls for adaptively secure augmented coin tossing and adaptively secure zero-knowledge protocols and obtain a constant round adaptively secure MPC protocol in the reverse firewall setting without setup. Along the way, we propose a new multi-party adaptively secure coin tossing protocol in the plain model, that is of independent interest.","lang":"eng"}],"date_published":"2021-12-01T00:00:00Z","article_processing_charge":"No","language":[{"iso":"eng"}],"doi":"10.1007/978-3-030-92075-3_12","project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"day":"01","alternative_title":["LNCS"],"author":[{"last_name":"Chakraborty","first_name":"Suvradip","full_name":"Chakraborty, Suvradip","id":"B9CD0494-D033-11E9-B219-A439E6697425"},{"full_name":"Ganesh, Chaya","first_name":"Chaya","last_name":"Ganesh"},{"first_name":"Mahak","full_name":"Pancholi, Mahak","last_name":"Pancholi"},{"last_name":"Sarkar","first_name":"Pratik","full_name":"Sarkar, Pratik"}],"type":"conference","ec_funded":1,"citation":{"short":"S. Chakraborty, C. Ganesh, M. Pancholi, P. Sarkar, in:, 27th International Conference on the Theory and Application of Cryptology and Information Security, Springer Nature, 2021, pp. 335–364.","ama":"Chakraborty S, Ganesh C, Pancholi M, Sarkar P. Reverse firewalls for adaptively secure MPC without setup. In: <i>27th International Conference on the Theory and Application of Cryptology and Information Security</i>. Vol 13091. Springer Nature; 2021:335-364. doi:<a href=\"https://doi.org/10.1007/978-3-030-92075-3_12\">10.1007/978-3-030-92075-3_12</a>","apa":"Chakraborty, S., Ganesh, C., Pancholi, M., &#38; Sarkar, P. (2021). Reverse firewalls for adaptively secure MPC without setup. In <i>27th International Conference on the Theory and Application of Cryptology and Information Security</i> (Vol. 13091, pp. 335–364). Virtual, Singapore: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-92075-3_12\">https://doi.org/10.1007/978-3-030-92075-3_12</a>","chicago":"Chakraborty, Suvradip, Chaya Ganesh, Mahak Pancholi, and Pratik Sarkar. “Reverse Firewalls for Adaptively Secure MPC without Setup.” In <i>27th International Conference on the Theory and Application of Cryptology and Information Security</i>, 13091:335–64. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-92075-3_12\">https://doi.org/10.1007/978-3-030-92075-3_12</a>.","ista":"Chakraborty S, Ganesh C, Pancholi M, Sarkar P. 2021. Reverse firewalls for adaptively secure MPC without setup. 27th International Conference on the Theory and Application of Cryptology and Information Security. ASIACRYPT: International Conference on Cryptology in Asia, LNCS, vol. 13091, 335–364.","ieee":"S. Chakraborty, C. Ganesh, M. Pancholi, and P. Sarkar, “Reverse firewalls for adaptively secure MPC without setup,” in <i>27th International Conference on the Theory and Application of Cryptology and Information Security</i>, Virtual, Singapore, 2021, vol. 13091, pp. 335–364.","mla":"Chakraborty, Suvradip, et al. “Reverse Firewalls for Adaptively Secure MPC without Setup.” <i>27th International Conference on the Theory and Application of Cryptology and Information Security</i>, vol. 13091, Springer Nature, 2021, pp. 335–64, doi:<a href=\"https://doi.org/10.1007/978-3-030-92075-3_12\">10.1007/978-3-030-92075-3_12</a>."},"conference":{"location":"Virtual, Singapore","name":"ASIACRYPT: International Conference on Cryptology in Asia","end_date":"2021-12-10","start_date":"2021-12-06"},"title":"Reverse firewalls for adaptively secure MPC without setup","quality_controlled":"1","department":[{"_id":"KrPi"}],"publication":"27th International Conference on the Theory and Application of Cryptology and Information Security","status":"public","intvolume":"     13091","publisher":"Springer Nature","isi":1,"month":"12","date_created":"2022-01-09T23:01:27Z","page":"335-364"},{"volume":12704,"oa":1,"main_file_link":[{"url":"https://eprint.iacr.org/2020/670","open_access":"1"}],"publication_status":"published","_id":"9826","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"}],"date_published":"2021-05-11T00:00:00Z","article_processing_charge":"No","publication_identifier":{"eissn":["16113349"],"issn":["03029743"],"isbn":["9783030755386"]},"scopus_import":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2023-02-23T14:09:56Z","year":"2021","oa_version":"Submitted Version","status":"public","intvolume":"     12704","publication":"Topics in Cryptology – CT-RSA 2021","department":[{"_id":"KrPi"},{"_id":"GradSch"}],"quality_controlled":"1","publisher":"Springer Nature","date_created":"2021-08-08T22:01:30Z","month":"05","page":"399-421","doi":"10.1007/978-3-030-75539-3_17","language":[{"iso":"eng"}],"project":[{"_id":"2564DBCA-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"665385","name":"International IST Doctoral Program"},{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"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).","author":[{"last_name":"Auerbach","full_name":"Auerbach, Benedikt","first_name":"Benedikt","orcid":"0000-0002-7553-6606","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425"},{"id":"B9CD0494-D033-11E9-B219-A439E6697425","full_name":"Chakraborty, Suvradip","first_name":"Suvradip","last_name":"Chakraborty"},{"id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","last_name":"Klein","first_name":"Karen","full_name":"Klein, Karen"},{"id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","last_name":"Pascual Perez","full_name":"Pascual Perez, Guillermo","first_name":"Guillermo"},{"last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654"},{"orcid":"0000-0003-3186-2482","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","last_name":"Walter","first_name":"Michael","full_name":"Walter, Michael"},{"last_name":"Yeo","first_name":"Michelle X","full_name":"Yeo, Michelle X","id":"2D82B818-F248-11E8-B48F-1D18A9856A87"}],"type":"conference","alternative_title":["LNCS"],"day":"11","title":"Inverse-Sybil attacks in automated contact tracing","conference":{"start_date":"2021-05-17","end_date":"2021-05-20","name":"CT-RSA: Cryptographers’ Track at the RSA Conference","location":"Virtual Event"},"citation":{"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.","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.","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>.","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>","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>"},"ec_funded":1},{"oa_version":"Submitted Version","year":"2021","external_id":{"isi":["000853016800008"],"arxiv":["2104.04293"]},"scopus_import":"1","date_updated":"2023-11-30T10:54:50Z","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publication_identifier":{"eisbn":["978-3-9031-7639-3"],"eissn":["1861-2288"],"isbn":["978-1-6654-4501-6"]},"abstract":[{"lang":"eng","text":"Payment channel networks are a promising approach to improve the scalability of cryptocurrencies: they allow to perform transactions in a peer-to-peer fashion, along multihop routes in the network, without requiring consensus on the blockchain. However, during the discovery of cost-efficient routes for the transaction, critical information may be revealed about the transacting entities. This paper initiates the study of privacy-preserving route discovery mechanisms for payment channel networks. In particular, we present LightPIR, an approach which allows a client to learn the shortest (or cheapest in terms of fees) path between two nodes without revealing any information about the endpoints of the transaction to the servers. The two main observations which allow for an efficient solution in LightPIR are that: (1) surprisingly, hub labelling algorithms – which were developed to preprocess “street network like” graphs so one can later efficiently compute shortest paths – also perform well for the graphs underlying payment channel networks, and that (2) hub labelling algorithms can be conveniently combined with private information retrieval. LightPIR relies on a simple hub labeling heuristic on top of existing hub labeling algorithms which leverages the specific topological features of cryptocurrency networks to further minimize storage and bandwidth overheads. In a case study considering the Lightning network, we show that our approach is an order of magnitude more efficient compared to a privacy-preserving baseline based on using private information retrieval on a database that stores all pairs shortest paths."}],"_id":"9969","date_published":"2021-06-21T00:00:00Z","arxiv":1,"article_processing_charge":"No","publication_status":"published","oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/2104.04293","open_access":"1"}],"day":"21","type":"conference","author":[{"first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654"},{"full_name":"Salem, Iosif","first_name":"Iosif","last_name":"Salem"},{"last_name":"Schmid","full_name":"Schmid, Stefan","first_name":"Stefan"},{"id":"2D82B818-F248-11E8-B48F-1D18A9856A87","full_name":"Yeo, Michelle X","first_name":"Michelle X","last_name":"Yeo"}],"citation":{"short":"K.Z. Pietrzak, I. Salem, S. Schmid, M.X. Yeo, in:, IEEE, 2021.","apa":"Pietrzak, K. Z., Salem, I., Schmid, S., &#38; Yeo, M. X. (2021). LightPIR: Privacy-preserving route discovery for payment channel networks. Presented at the 2021 IFIP Networking Conference (IFIP Networking), Espoo and Helsinki, Finland: IEEE. <a href=\"https://doi.org/10.23919/IFIPNetworking52078.2021.9472205\">https://doi.org/10.23919/IFIPNetworking52078.2021.9472205</a>","ama":"Pietrzak KZ, Salem I, Schmid S, Yeo MX. LightPIR: Privacy-preserving route discovery for payment channel networks. In: IEEE; 2021. doi:<a href=\"https://doi.org/10.23919/IFIPNetworking52078.2021.9472205\">10.23919/IFIPNetworking52078.2021.9472205</a>","ista":"Pietrzak KZ, Salem I, Schmid S, Yeo MX. 2021. LightPIR: Privacy-preserving route discovery for payment channel networks. 2021 IFIP Networking Conference (IFIP Networking).","ieee":"K. Z. Pietrzak, I. Salem, S. Schmid, and M. X. Yeo, “LightPIR: Privacy-preserving route discovery for payment channel networks,” presented at the 2021 IFIP Networking Conference (IFIP Networking), Espoo and Helsinki, Finland, 2021.","chicago":"Pietrzak, Krzysztof Z, Iosif Salem, Stefan Schmid, and Michelle X Yeo. “LightPIR: Privacy-Preserving Route Discovery for Payment Channel Networks.” IEEE, 2021. <a href=\"https://doi.org/10.23919/IFIPNetworking52078.2021.9472205\">https://doi.org/10.23919/IFIPNetworking52078.2021.9472205</a>.","mla":"Pietrzak, Krzysztof Z., et al. <i>LightPIR: Privacy-Preserving Route Discovery for Payment Channel Networks</i>. IEEE, 2021, doi:<a href=\"https://doi.org/10.23919/IFIPNetworking52078.2021.9472205\">10.23919/IFIPNetworking52078.2021.9472205</a>."},"ec_funded":1,"title":"LightPIR: Privacy-preserving route discovery for payment channel networks","conference":{"location":"Espoo and Helsinki, Finland","end_date":"2021-06-24","start_date":"2021-06-21","name":"2021 IFIP Networking Conference (IFIP Networking)"},"language":[{"iso":"eng"}],"doi":"10.23919/IFIPNetworking52078.2021.9472205","project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"related_material":{"record":[{"relation":"dissertation_contains","id":"14506","status":"public"}]},"month":"06","date_created":"2021-08-29T22:01:16Z","quality_controlled":"1","department":[{"_id":"KrPi"}],"status":"public","publisher":"IEEE","isi":1},{"oa":1,"publication_status":"published","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"file_date_updated":"2020-07-14T12:48:04Z","article_processing_charge":"No","_id":"7896","date_published":"2020-05-25T00:00:00Z","abstract":[{"lang":"eng","text":"A search problem lies in the complexity class FNP if a solution to the given instance of the problem can be verified efficiently. The complexity class TFNP consists of all search problems in FNP that are total in the sense that a solution is guaranteed to exist. TFNP contains a host of interesting problems from fields such as algorithmic game theory, computational topology, number theory and combinatorics. Since TFNP is a semantic class, it is unlikely to have a complete problem. Instead, one studies its syntactic subclasses which are defined based on the combinatorial principle used to argue totality. Of particular interest is the subclass PPAD, which contains important problems\r\nlike computing Nash equilibrium for bimatrix games and computational counterparts of several fixed-point theorems as complete. In the thesis, we undertake the study of averagecase hardness of TFNP, and in particular its subclass PPAD.\r\nAlmost nothing was known about average-case hardness of PPAD before a series of recent results showed how to achieve it using a cryptographic primitive called program obfuscation.\r\nHowever, it is currently not known how to construct program obfuscation from standard cryptographic assumptions. Therefore, it is desirable to relax the assumption under which average-case hardness of PPAD can be shown. In the thesis we take a step in this direction. First, we show that assuming the (average-case) hardness of a numbertheoretic\r\nproblem related to factoring of integers, which we call Iterated-Squaring, PPAD is hard-on-average in the random-oracle model. Then we strengthen this result to show that the average-case hardness of PPAD reduces to the (adaptive) soundness of the Fiat-Shamir Transform, a well-known technique used to compile a public-coin interactive protocol into a non-interactive one. As a corollary, we obtain average-case hardness for PPAD in the random-oracle model assuming the worst-case hardness of #SAT. Moreover, the above results can all be strengthened to obtain average-case hardness for the class CLS ⊆ PPAD.\r\nOur main technical contribution is constructing incrementally-verifiable procedures for computing Iterated-Squaring and #SAT. By incrementally-verifiable, we mean that every intermediate state of the computation includes a proof of its correctness, and the proof can be updated and verified in polynomial time. Previous constructions of such procedures relied on strong, non-standard assumptions. Instead, we introduce a technique called recursive proof-merging to obtain the same from weaker assumptions. "}],"file":[{"content_type":"application/pdf","relation":"main_file","file_id":"7897","date_created":"2020-05-26T14:08:13Z","file_name":"2020_Thesis_Kamath.pdf","file_size":1622742,"creator":"dernst","checksum":"b39e2e1c376f5819b823fb7077491c64","date_updated":"2020-07-14T12:48:04Z","access_level":"open_access"},{"file_id":"7898","relation":"source_file","content_type":"application/x-zip-compressed","date_created":"2020-05-26T14:08:23Z","file_size":15301529,"creator":"dernst","file_name":"Thesis_Kamath.zip","checksum":"8b26ba729c1a85ac6bea775f5d73cdc7","access_level":"closed","date_updated":"2020-07-14T12:48:04Z"}],"publication_identifier":{"issn":["2663-337X"]},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","date_updated":"2023-09-07T13:15:55Z","year":"2020","has_accepted_license":"1","oa_version":"Published Version","degree_awarded":"PhD","publisher":"Institute of Science and Technology Austria","status":"public","department":[{"_id":"KrPi"}],"page":"126","date_created":"2020-05-26T14:08:55Z","supervisor":[{"last_name":"Pietrzak","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"}],"month":"05","project":[{"_id":"258C570E-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"259668","name":"Provable Security for Physical Cryptography"},{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"related_material":{"record":[{"id":"6677","relation":"part_of_dissertation","status":"public"}]},"doi":"10.15479/AT:ISTA:7896","ddc":["000"],"language":[{"iso":"eng"}],"title":"On the average-case hardness of total search problems","ec_funded":1,"citation":{"apa":"Kamath Hosdurg, C. (2020). <i>On the average-case hardness of total search problems</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:7896\">https://doi.org/10.15479/AT:ISTA:7896</a>","ama":"Kamath Hosdurg C. On the average-case hardness of total search problems. 2020. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:7896\">10.15479/AT:ISTA:7896</a>","short":"C. Kamath Hosdurg, On the Average-Case Hardness of Total Search Problems, Institute of Science and Technology Austria, 2020.","mla":"Kamath Hosdurg, Chethan. <i>On the Average-Case Hardness of Total Search Problems</i>. Institute of Science and Technology Austria, 2020, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:7896\">10.15479/AT:ISTA:7896</a>.","ista":"Kamath Hosdurg C. 2020. On the average-case hardness of total search problems. Institute of Science and Technology Austria.","ieee":"C. Kamath Hosdurg, “On the average-case hardness of total search problems,” Institute of Science and Technology Austria, 2020.","chicago":"Kamath Hosdurg, Chethan. “On the Average-Case Hardness of Total Search Problems.” Institute of Science and Technology Austria, 2020. <a href=\"https://doi.org/10.15479/AT:ISTA:7896\">https://doi.org/10.15479/AT:ISTA:7896</a>."},"alternative_title":["ISTA Thesis"],"type":"dissertation","author":[{"last_name":"Kamath Hosdurg","full_name":"Kamath Hosdurg, Chethan","first_name":"Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87"}],"day":"25"},{"date_updated":"2023-09-05T15:06:40Z","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","external_id":{"isi":["000828688000016"]},"publication_identifier":{"isbn":["9783030457266","9783030457273"],"issn":["0302-9743"],"eissn":["1611-3349"]},"year":"2020","oa_version":"Submitted Version","publication_status":"published","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2019/364"}],"oa":1,"volume":12107,"article_processing_charge":"No","_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."}],"date_published":"2020-05-01T00:00:00Z","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Teaching Old Crypto New Tricks","grant_number":"682815"}],"language":[{"iso":"eng"}],"doi":"10.1007/978-3-030-45727-3_16","ec_funded":1,"citation":{"mla":"Auerbach, Benedikt, et al. “Everybody’s a Target: Scalability in Public-Key Encryption.” <i>Advances in Cryptology – EUROCRYPT 2020</i>, vol. 12107, Springer Nature, 2020, pp. 475–506, doi:<a href=\"https://doi.org/10.1007/978-3-030-45727-3_16\">10.1007/978-3-030-45727-3_16</a>.","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.","ieee":"B. Auerbach, F. Giacon, and E. Kiltz, “Everybody’s a target: Scalability in public-key encryption,” in <i>Advances in Cryptology – EUROCRYPT 2020</i>, 2020, vol. 12107, pp. 475–506.","chicago":"Auerbach, Benedikt, Federico Giacon, and Eike Kiltz. “Everybody’s a Target: Scalability in Public-Key Encryption.” In <i>Advances in Cryptology – EUROCRYPT 2020</i>, 12107:475–506. Springer Nature, 2020. <a href=\"https://doi.org/10.1007/978-3-030-45727-3_16\">https://doi.org/10.1007/978-3-030-45727-3_16</a>.","apa":"Auerbach, B., Giacon, F., &#38; Kiltz, E. (2020). Everybody’s a target: Scalability in public-key encryption. In <i>Advances in Cryptology – EUROCRYPT 2020</i> (Vol. 12107, pp. 475–506). Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-45727-3_16\">https://doi.org/10.1007/978-3-030-45727-3_16</a>","ama":"Auerbach B, Giacon F, Kiltz E. Everybody’s a target: Scalability in public-key encryption. In: <i>Advances in Cryptology – EUROCRYPT 2020</i>. Vol 12107. Springer Nature; 2020:475-506. doi:<a href=\"https://doi.org/10.1007/978-3-030-45727-3_16\">10.1007/978-3-030-45727-3_16</a>","short":"B. Auerbach, F. Giacon, E. Kiltz, in:, Advances in Cryptology – EUROCRYPT 2020, Springer Nature, 2020, pp. 475–506."},"conference":{"start_date":"2020-05-11","end_date":"2020-05-15","name":"EUROCRYPT: Theory and Applications of Cryptographic Techniques"},"title":"Everybody’s a target: Scalability in public-key encryption","day":"01","alternative_title":["LNCS"],"type":"conference","author":[{"id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","orcid":"0000-0002-7553-6606","full_name":"Auerbach, Benedikt","first_name":"Benedikt","last_name":"Auerbach"},{"full_name":"Giacon, Federico","first_name":"Federico","last_name":"Giacon"},{"last_name":"Kiltz","full_name":"Kiltz, Eike","first_name":"Eike"}],"publisher":"Springer Nature","isi":1,"quality_controlled":"1","department":[{"_id":"KrPi"}],"publication":"Advances in Cryptology – EUROCRYPT 2020","intvolume":"     12107","status":"public","page":"475-506","month":"05","date_created":"2020-06-15T07:13:37Z"},{"publication":"Advances in Cryptology – CRYPTO 2020","quality_controlled":"1","department":[{"_id":"KrPi"}],"status":"public","intvolume":"     12171","publisher":"Springer Nature","month":"08","date_created":"2020-08-30T22:01:12Z","page":"732-762","language":[{"iso":"eng"}],"doi":"10.1007/978-3-030-56880-1_26","project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"acknowledgement":"We would like to thank the anonymous reviewers for their helpful comments and suggestions. The work was initiated while the first author was in IIT Madras, India. Part of this work was done while the author was visiting the University of Warsaw. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT) and from the Foundation for Polish Science under grant TEAM/2016-1/4 founded within the UE 2014–2020 Smart Growth Operational Program. The last author was supported by the Independent Research Fund Denmark project BETHE and the Concordium Blockchain Research Center, Aarhus University, Denmark.","day":"10","author":[{"last_name":"Chakraborty","full_name":"Chakraborty, Suvradip","first_name":"Suvradip","id":"B9CD0494-D033-11E9-B219-A439E6697425"},{"last_name":"Dziembowski","full_name":"Dziembowski, Stefan","first_name":"Stefan"},{"first_name":"Jesper Buus","full_name":"Nielsen, Jesper Buus","last_name":"Nielsen"}],"type":"conference","alternative_title":["LNCS"],"citation":{"mla":"Chakraborty, Suvradip, et al. “Reverse Firewalls for Actively Secure MPCs.” <i>Advances in Cryptology – CRYPTO 2020</i>, vol. 12171, Springer Nature, 2020, pp. 732–62, doi:<a href=\"https://doi.org/10.1007/978-3-030-56880-1_26\">10.1007/978-3-030-56880-1_26</a>.","chicago":"Chakraborty, Suvradip, Stefan Dziembowski, and Jesper Buus Nielsen. “Reverse Firewalls for Actively Secure MPCs.” In <i>Advances in Cryptology – CRYPTO 2020</i>, 12171:732–62. Springer Nature, 2020. <a href=\"https://doi.org/10.1007/978-3-030-56880-1_26\">https://doi.org/10.1007/978-3-030-56880-1_26</a>.","ista":"Chakraborty S, Dziembowski S, Nielsen JB. 2020. Reverse firewalls for actively secure MPCs. Advances in Cryptology – CRYPTO 2020. CRYPTO: Annual International Cryptology Conference, LNCS, vol. 12171, 732–762.","ieee":"S. Chakraborty, S. Dziembowski, and J. B. Nielsen, “Reverse firewalls for actively secure MPCs,” in <i>Advances in Cryptology – CRYPTO 2020</i>, Santa Barbara, CA, United States, 2020, vol. 12171, pp. 732–762.","ama":"Chakraborty S, Dziembowski S, Nielsen JB. Reverse firewalls for actively secure MPCs. In: <i>Advances in Cryptology – CRYPTO 2020</i>. Vol 12171. Springer Nature; 2020:732-762. doi:<a href=\"https://doi.org/10.1007/978-3-030-56880-1_26\">10.1007/978-3-030-56880-1_26</a>","apa":"Chakraborty, S., Dziembowski, S., &#38; Nielsen, J. B. (2020). Reverse firewalls for actively secure MPCs. In <i>Advances in Cryptology – CRYPTO 2020</i> (Vol. 12171, pp. 732–762). Santa Barbara, CA, United States: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-56880-1_26\">https://doi.org/10.1007/978-3-030-56880-1_26</a>","short":"S. Chakraborty, S. Dziembowski, J.B. Nielsen, in:, Advances in Cryptology – CRYPTO 2020, Springer Nature, 2020, pp. 732–762."},"ec_funded":1,"title":"Reverse firewalls for actively secure MPCs","conference":{"start_date":"2020-08-17","end_date":"2020-08-21","name":"CRYPTO: Annual International Cryptology Conference","location":"Santa Barbara, CA, United States"},"volume":12171,"publication_status":"published","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2019/1317"}],"oa":1,"date_published":"2020-08-10T00:00:00Z","_id":"8322","abstract":[{"text":"Reverse firewalls were introduced at Eurocrypt 2015 by Miro-nov and Stephens-Davidowitz, as a method for protecting cryptographic protocols against attacks on the devices of the honest parties. In a nutshell: a reverse firewall is placed outside of a device and its goal is to “sanitize” the messages sent by it, in such a way that a malicious device cannot leak its secrets to the outside world. It is typically assumed that the cryptographic devices are attacked in a “functionality-preserving way” (i.e. informally speaking, the functionality of the protocol remains unchanged under this attacks). In their paper, Mironov and Stephens-Davidowitz construct a protocol for passively-secure two-party computations with firewalls, leaving extension of this result to stronger models as an open question.\r\nIn this paper, we address this problem by constructing a protocol for secure computation with firewalls that has two main advantages over the original protocol from Eurocrypt 2015. Firstly, it is a multiparty computation protocol (i.e. it works for an arbitrary number n of the parties, and not just for 2). Secondly, it is secure in much stronger corruption settings, namely in the active corruption model. More precisely: we consider an adversary that can fully corrupt up to 𝑛−1 parties, while the remaining parties are corrupt in a functionality-preserving way.\r\nOur core techniques are: malleable commitments and malleable non-interactive zero-knowledge, which in particular allow us to create a novel protocol for multiparty augmented coin-tossing into the well with reverse firewalls (that is based on a protocol of Lindell from Crypto 2001).","lang":"eng"}],"article_processing_charge":"No","scopus_import":"1","date_updated":"2021-01-12T08:18:08Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"eissn":["16113349"],"issn":["03029743"],"isbn":["9783030568795"]},"oa_version":"Preprint","year":"2020"},{"status":"public","intvolume":"     12110","publication":"23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography","quality_controlled":"1","department":[{"_id":"KrPi"}],"publisher":"Springer Nature","date_created":"2020-09-06T22:01:13Z","month":"05","page":"623-651","doi":"10.1007/978-3-030-45374-9_21","language":[{"iso":"eng"}],"project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"author":[{"first_name":"Nicholas","full_name":"Genise, Nicholas","last_name":"Genise"},{"full_name":"Micciancio, Daniele","first_name":"Daniele","last_name":"Micciancio"},{"first_name":"Chris","full_name":"Peikert, Chris","last_name":"Peikert"},{"full_name":"Walter, Michael","first_name":"Michael","last_name":"Walter","orcid":"0000-0003-3186-2482","id":"488F98B0-F248-11E8-B48F-1D18A9856A87"}],"type":"conference","alternative_title":["LNCS"],"day":"15","title":"Improved discrete Gaussian and subgaussian analysis for lattice cryptography","conference":{"location":"Edinburgh, United Kingdom","name":"PKC: Public-Key Cryptography","end_date":"2020-05-07","start_date":"2020-05-04"},"citation":{"ieee":"N. Genise, D. Micciancio, C. Peikert, and M. Walter, “Improved discrete Gaussian and subgaussian analysis for lattice cryptography,” in <i>23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography</i>, Edinburgh, United Kingdom, 2020, vol. 12110, pp. 623–651.","ista":"Genise N, Micciancio D, Peikert C, Walter M. 2020. Improved discrete Gaussian and subgaussian analysis for lattice cryptography. 23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography. PKC: Public-Key Cryptography, LNCS, vol. 12110, 623–651.","chicago":"Genise, Nicholas, Daniele Micciancio, Chris Peikert, and Michael Walter. “Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography.” In <i>23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography</i>, 12110:623–51. Springer Nature, 2020. <a href=\"https://doi.org/10.1007/978-3-030-45374-9_21\">https://doi.org/10.1007/978-3-030-45374-9_21</a>.","mla":"Genise, Nicholas, et al. “Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography.” <i>23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography</i>, vol. 12110, Springer Nature, 2020, pp. 623–51, doi:<a href=\"https://doi.org/10.1007/978-3-030-45374-9_21\">10.1007/978-3-030-45374-9_21</a>.","short":"N. Genise, D. Micciancio, C. Peikert, M. Walter, in:, 23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography, Springer Nature, 2020, pp. 623–651.","apa":"Genise, N., Micciancio, D., Peikert, C., &#38; Walter, M. (2020). Improved discrete Gaussian and subgaussian analysis for lattice cryptography. In <i>23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography</i> (Vol. 12110, pp. 623–651). Edinburgh, United Kingdom: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-45374-9_21\">https://doi.org/10.1007/978-3-030-45374-9_21</a>","ama":"Genise N, Micciancio D, Peikert C, Walter M. Improved discrete Gaussian and subgaussian analysis for lattice cryptography. In: <i>23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography</i>. Vol 12110. Springer Nature; 2020:623-651. doi:<a href=\"https://doi.org/10.1007/978-3-030-45374-9_21\">10.1007/978-3-030-45374-9_21</a>"},"ec_funded":1,"volume":12110,"main_file_link":[{"url":"https://eprint.iacr.org/2020/337","open_access":"1"}],"oa":1,"publication_status":"published","date_published":"2020-05-15T00:00:00Z","_id":"8339","abstract":[{"lang":"eng","text":"Discrete Gaussian distributions over lattices are central to lattice-based cryptography, and to the computational and mathematical aspects of lattices more broadly. The literature contains a wealth of useful theorems about the behavior of discrete Gaussians under convolutions and related operations. Yet despite their structural similarities, most of these theorems are formally incomparable, and their proofs tend to be monolithic and written nearly “from scratch,” making them unnecessarily hard to verify, understand, and extend.\r\nIn this work we present a modular framework for analyzing linear operations on discrete Gaussian distributions. The framework abstracts away the particulars of Gaussians, and usually reduces proofs to the choice of appropriate linear transformations and elementary linear algebra. To showcase the approach, we establish several general properties of discrete Gaussians, and show how to obtain all prior convolution theorems (along with some new ones) as straightforward corollaries. As another application, we describe a self-reduction for Learning With Errors (LWE) that uses a fixed number of samples to generate an unlimited number of additional ones (having somewhat larger error). The distinguishing features of our reduction are its simple analysis in our framework, and its exclusive use of discrete Gaussians without any loss in parameters relative to a prior mixed discrete-and-continuous approach.\r\nAs a contribution of independent interest, for subgaussian random matrices we prove a singular value concentration bound with explicitly stated constants, and we give tighter heuristics for specific distributions that are commonly used for generating lattice trapdoors. These bounds yield improvements in the concrete bit-security estimates for trapdoor lattice cryptosystems."}],"article_processing_charge":"No","publication_identifier":{"eissn":["16113349"],"issn":["03029743"],"isbn":["9783030453732"]},"scopus_import":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2023-02-23T13:31:06Z","oa_version":"Preprint","year":"2020"},{"oa_version":"Preprint","year":"2020","publication_identifier":{"eissn":["16113349"],"issn":["03029743"],"isbn":["9783030652760"]},"date_updated":"2023-08-24T11:08:58Z","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","scopus_import":"1","external_id":{"isi":["000927592800001"]},"article_processing_charge":"No","_id":"8987","date_published":"2020-12-08T00:00:00Z","abstract":[{"lang":"eng","text":"Currently several projects aim at designing and implementing protocols for privacy preserving automated contact tracing to help fight the current pandemic. Those proposal are quite similar, and in their most basic form basically propose an app for mobile phones which broadcasts frequently changing pseudorandom identifiers via (low energy) Bluetooth, and at the same time, the app stores IDs broadcast by phones in its proximity. Only if a user is tested positive, they upload either the beacons they did broadcast (which is the case in decentralized proposals as DP-3T, east and west coast PACT or Covid watch) or received (as in Popp-PT or ROBERT) during the last two weeks or so.\r\n\r\nVaudenay [eprint 2020/399] observes that this basic scheme (he considers the DP-3T proposal) succumbs to relay and even replay attacks, and proposes more complex interactive schemes which prevent those attacks without giving up too many privacy aspects. Unfortunately interaction is problematic for this application for efficiency and security reasons. The countermeasures that have been suggested so far are either not practical or give up on key privacy aspects. We propose a simple non-interactive variant of the basic protocol that\r\n(security) Provably prevents replay and (if location data is available) relay attacks.\r\n(privacy) The data of all parties (even jointly) reveals no information on the location or time where encounters happened.\r\n(efficiency) The broadcasted message can fit into 128 bits and uses only basic crypto (commitments and secret key authentication).\r\n\r\nTowards this end we introduce the concept of “delayed authentication”, which basically is a message authentication code where verification can be done in two steps, where the first doesn’t require the key, and the second doesn’t require the message."}],"oa":1,"main_file_link":[{"url":"https://eprint.iacr.org/2020/418","open_access":"1"}],"publication_status":"published","volume":12578,"conference":{"location":"Bangalore, India","end_date":"2020-12-16","start_date":"2020-12-13","name":"INDOCRYPT: International Conference on Cryptology in India"},"title":"Delayed authentication: Preventing replay and relay attacks in private contact tracing","ec_funded":1,"citation":{"ieee":"K. Z. Pietrzak, “Delayed authentication: Preventing replay and relay attacks in private contact tracing,” in <i>Progress in Cryptology</i>, Bangalore, India, 2020, vol. 12578, pp. 3–15.","ista":"Pietrzak KZ. 2020. Delayed authentication: Preventing replay and relay attacks in private contact tracing. Progress in Cryptology. INDOCRYPT: International Conference on Cryptology in IndiaLNCS vol. 12578, 3–15.","chicago":"Pietrzak, Krzysztof Z. “Delayed Authentication: Preventing Replay and Relay Attacks in Private Contact Tracing.” In <i>Progress in Cryptology</i>, 12578:3–15. LNCS. Springer Nature, 2020. <a href=\"https://doi.org/10.1007/978-3-030-65277-7_1\">https://doi.org/10.1007/978-3-030-65277-7_1</a>.","mla":"Pietrzak, Krzysztof Z. “Delayed Authentication: Preventing Replay and Relay Attacks in Private Contact Tracing.” <i>Progress in Cryptology</i>, vol. 12578, Springer Nature, 2020, pp. 3–15, doi:<a href=\"https://doi.org/10.1007/978-3-030-65277-7_1\">10.1007/978-3-030-65277-7_1</a>.","short":"K.Z. Pietrzak, in:, Progress in Cryptology, Springer Nature, 2020, pp. 3–15.","apa":"Pietrzak, K. Z. (2020). Delayed authentication: Preventing replay and relay attacks in private contact tracing. In <i>Progress in Cryptology</i> (Vol. 12578, pp. 3–15). Bangalore, India: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-65277-7_1\">https://doi.org/10.1007/978-3-030-65277-7_1</a>","ama":"Pietrzak KZ. Delayed authentication: Preventing replay and relay attacks in private contact tracing. In: <i>Progress in Cryptology</i>. Vol 12578. LNCS. Springer Nature; 2020:3-15. doi:<a href=\"https://doi.org/10.1007/978-3-030-65277-7_1\">10.1007/978-3-030-65277-7_1</a>"},"author":[{"last_name":"Pietrzak","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654"}],"type":"conference","day":"08","project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"doi":"10.1007/978-3-030-65277-7_1","language":[{"iso":"eng"}],"page":"3-15","date_created":"2021-01-03T23:01:23Z","series_title":"LNCS","month":"12","isi":1,"publisher":"Springer Nature","intvolume":"     12578","status":"public","department":[{"_id":"KrPi"}],"quality_controlled":"1","publication":"Progress in Cryptology"},{"month":"06","date_created":"2019-07-24T09:20:53Z","page":"1103-1114","quality_controlled":"1","department":[{"_id":"KrPi"}],"publication":"Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019","status":"public","publisher":"ACM Press","isi":1,"day":"01","author":[{"first_name":"Arka Rai","full_name":"Choudhuri, Arka Rai","last_name":"Choudhuri"},{"last_name":"Hubáček","first_name":"Pavel","full_name":"Hubáček, Pavel"},{"id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","last_name":"Kamath Hosdurg","full_name":"Kamath Hosdurg, Chethan","first_name":"Chethan"},{"last_name":"Pietrzak","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654"},{"first_name":"Alon","full_name":"Rosen, Alon","last_name":"Rosen"},{"last_name":"Rothblum","full_name":"Rothblum, Guy N.","first_name":"Guy N."}],"type":"conference","ec_funded":1,"citation":{"mla":"Choudhuri, Arka Rai, et al. “Finding a Nash Equilibrium Is No Easier than Breaking Fiat-Shamir.” <i>Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019</i>, ACM Press, 2019, pp. 1103–14, doi:<a href=\"https://doi.org/10.1145/3313276.3316400\">10.1145/3313276.3316400</a>.","chicago":"Choudhuri, Arka Rai, Pavel Hubáček, Chethan Kamath Hosdurg, Krzysztof Z Pietrzak, Alon Rosen, and Guy N. Rothblum. “Finding a Nash Equilibrium Is No Easier than Breaking Fiat-Shamir.” In <i>Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019</i>, 1103–14. ACM Press, 2019. <a href=\"https://doi.org/10.1145/3313276.3316400\">https://doi.org/10.1145/3313276.3316400</a>.","ieee":"A. R. Choudhuri, P. Hubáček, C. Kamath Hosdurg, K. Z. Pietrzak, A. Rosen, and G. N. Rothblum, “Finding a Nash equilibrium is no easier than breaking Fiat-Shamir,” in <i>Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019</i>, Phoenix, AZ, United States, 2019, pp. 1103–1114.","ista":"Choudhuri AR, Hubáček P, Kamath Hosdurg C, Pietrzak KZ, Rosen A, Rothblum GN. 2019. Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019. STOC: Symposium on Theory of Computing, 1103–1114.","ama":"Choudhuri AR, Hubáček P, Kamath Hosdurg C, Pietrzak KZ, Rosen A, Rothblum GN. Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. In: <i>Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019</i>. ACM Press; 2019:1103-1114. doi:<a href=\"https://doi.org/10.1145/3313276.3316400\">10.1145/3313276.3316400</a>","apa":"Choudhuri, A. R., Hubáček, P., Kamath Hosdurg, C., Pietrzak, K. Z., Rosen, A., &#38; Rothblum, G. N. (2019). Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. In <i>Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019</i> (pp. 1103–1114). Phoenix, AZ, United States: ACM Press. <a href=\"https://doi.org/10.1145/3313276.3316400\">https://doi.org/10.1145/3313276.3316400</a>","short":"A.R. Choudhuri, P. Hubáček, C. Kamath Hosdurg, K.Z. Pietrzak, A. Rosen, G.N. Rothblum, in:, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019, ACM Press, 2019, pp. 1103–1114."},"conference":{"name":"STOC: Symposium on Theory of Computing","end_date":"2019-06-26","start_date":"2019-06-23","location":"Phoenix, AZ, United States"},"title":"Finding a Nash equilibrium is no easier than breaking Fiat-Shamir","language":[{"iso":"eng"}],"doi":"10.1145/3313276.3316400","related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"7896"}]},"project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"abstract":[{"lang":"eng","text":"The Fiat-Shamir heuristic transforms a public-coin interactive proof into a non-interactive argument, by replacing the verifier with a cryptographic hash function that is applied to the protocol’s transcript. Constructing hash functions for which this transformation is sound is a central and long-standing open question in cryptography.\r\n\r\nWe show that solving the END−OF−METERED−LINE problem is no easier than breaking the soundness of the Fiat-Shamir transformation when applied to the sumcheck protocol. In particular, if the transformed protocol is sound, then any hard problem in #P gives rise to a hard distribution in the class CLS, which is contained in PPAD. Our result opens up the possibility of sampling moderately-sized games for which it is hard to find a Nash equilibrium, by reducing the inversion of appropriately chosen one-way functions to #SAT.\r\n\r\nOur main technical contribution is a stateful incrementally verifiable procedure that, given a SAT instance over n variables, counts the number of satisfying assignments. This is accomplished via an exponential sequence of small steps, each computable in time poly(n). Incremental verifiability means that each intermediate state includes a sumcheck-based proof of its correctness, and the proof can be updated and verified in time poly(n)."}],"_id":"6677","date_published":"2019-06-01T00:00:00Z","article_processing_charge":"No","publication_status":"published","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2019/549"}],"oa":1,"year":"2019","oa_version":"Preprint","date_updated":"2023-09-07T13:15:55Z","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","external_id":{"isi":["000523199100100"]},"scopus_import":"1","publication_identifier":{"isbn":["9781450367059"]}},{"oa":1,"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2019/068"}],"publication_status":"published","volume":11627,"article_processing_charge":"No","_id":"6726","date_published":"2019-06-29T00:00:00Z","abstract":[{"lang":"eng","text":"Randomness is an essential part of any secure cryptosystem, but many constructions rely on distributions that are not uniform. This is particularly true for lattice based cryptosystems, which more often than not make use of discrete Gaussian distributions over the integers. For practical purposes it is crucial to evaluate the impact that approximation errors have on the security of a scheme to provide the best possible trade-off between security and performance. Recent years have seen surprising results allowing to use relatively low precision while maintaining high levels of security. A key insight in these results is that sampling a distribution with low relative error can provide very strong security guarantees. Since floating point numbers provide guarantees on the relative approximation error, they seem a suitable tool in this setting, but it is not obvious which sampling algorithms can actually profit from them. While previous works have shown that inversion sampling can be adapted to provide a low relative error (Pöppelmann et al., CHES 2014; Prest, ASIACRYPT 2017), other works have called into question if this is possible for other sampling techniques (Zheng et al., Eprint report 2018/309). In this work, we consider all sampling algorithms that are popular in the cryptographic setting and analyze the relationship of floating point precision and the resulting relative error. We show that all of the algorithms either natively achieve a low relative error or can be adapted to do so."}],"publication_identifier":{"eisbn":["978-3-0302-3696-0"],"issn":["0302-9743","1611-3349"],"isbn":["978-3-0302-3695-3"]},"scopus_import":"1","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","date_updated":"2023-02-23T12:50:15Z","editor":[{"last_name":"Buchmann","full_name":"Buchmann, J","first_name":"J"},{"first_name":"A","full_name":"Nitaj, A","last_name":"Nitaj"},{"full_name":"Rachidi, T","first_name":"T","last_name":"Rachidi"}],"oa_version":"Preprint","year":"2019","publisher":"Springer Nature","intvolume":"     11627","status":"public","publication":"Progress in Cryptology – AFRICACRYPT 2019","quality_controlled":"1","department":[{"_id":"KrPi"}],"page":"157-180","series_title":"LNCS","date_created":"2019-07-29T12:25:31Z","month":"06","place":"Cham","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Teaching Old Crypto New Tricks","grant_number":"682815"}],"doi":"10.1007/978-3-030-23696-0_9","language":[{"iso":"eng"}],"title":"Sampling the integers with low relative error","conference":{"location":"Rabat, Morocco","name":"AFRICACRYPT: International Conference on Cryptology in Africa","end_date":"2019-07-11","start_date":"2019-07-09"},"citation":{"mla":"Walter, Michael. “Sampling the Integers with Low Relative Error.” <i>Progress in Cryptology – AFRICACRYPT 2019</i>, edited by J Buchmann et al., vol. 11627, Springer Nature, 2019, pp. 157–80, doi:<a href=\"https://doi.org/10.1007/978-3-030-23696-0_9\">10.1007/978-3-030-23696-0_9</a>.","chicago":"Walter, Michael. “Sampling the Integers with Low Relative Error.” In <i>Progress in Cryptology – AFRICACRYPT 2019</i>, edited by J Buchmann, A Nitaj, and T Rachidi, 11627:157–80. LNCS. Cham: Springer Nature, 2019. <a href=\"https://doi.org/10.1007/978-3-030-23696-0_9\">https://doi.org/10.1007/978-3-030-23696-0_9</a>.","ista":"Walter M. 2019.Sampling the integers with low relative error. In: Progress in Cryptology – AFRICACRYPT 2019. vol. 11627, 157–180.","ieee":"M. Walter, “Sampling the integers with low relative error,” in <i>Progress in Cryptology – AFRICACRYPT 2019</i>, vol. 11627, J. Buchmann, A. Nitaj, and T. Rachidi, Eds. Cham: Springer Nature, 2019, pp. 157–180.","ama":"Walter M. Sampling the integers with low relative error. In: Buchmann J, Nitaj A, Rachidi T, eds. <i>Progress in Cryptology – AFRICACRYPT 2019</i>. Vol 11627. LNCS. Cham: Springer Nature; 2019:157-180. doi:<a href=\"https://doi.org/10.1007/978-3-030-23696-0_9\">10.1007/978-3-030-23696-0_9</a>","apa":"Walter, M. (2019). Sampling the integers with low relative error. In J. Buchmann, A. Nitaj, &#38; T. Rachidi (Eds.), <i>Progress in Cryptology – AFRICACRYPT 2019</i> (Vol. 11627, pp. 157–180). Cham: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-23696-0_9\">https://doi.org/10.1007/978-3-030-23696-0_9</a>","short":"M. Walter, in:, J. Buchmann, A. Nitaj, T. Rachidi (Eds.), Progress in Cryptology – AFRICACRYPT 2019, Springer Nature, Cham, 2019, pp. 157–180."},"ec_funded":1,"type":"book_chapter","author":[{"orcid":"0000-0003-3186-2482","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","first_name":"Michael","full_name":"Walter, Michael","last_name":"Walter"}],"day":"29"}]