[{"related_material":{"record":[{"id":"10035","status":"public","relation":"dissertation_contains"}]},"ec_funded":1,"abstract":[{"lang":"eng","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."}],"author":[{"full_name":"Kamath Hosdurg, Chethan","first_name":"Chethan","last_name":"Kamath Hosdurg","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87"},{"id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","last_name":"Klein","first_name":"Karen","full_name":"Klein, Karen"},{"full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Wichs","first_name":"Daniel","full_name":"Wichs, Daniel"}],"_id":"10041","conference":{"name":"CRYPTO: Annual International Cryptology Conference","end_date":"2021-08-20","location":"Virtual","start_date":"2021-08-16"},"date_created":"2021-09-23T14:06:15Z","date_published":"2021-08-11T00:00:00Z","language":[{"iso":"eng"}],"month":"08","doi":"10.1007/978-3-030-84245-1_17","year":"2021","type":"conference","date_updated":"2023-09-07T13:32:11Z","place":"Cham","publication_status":"published","intvolume":"     12826","oa":1,"citation":{"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>.","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.","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.","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.","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>","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>","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>."},"day":"11","publication_identifier":{"issn":["0302-9743"],"eissn":["1611-3349"],"eisbn":["978-3-030-84245-1"],"isbn":["978-3-030-84244-4"]},"quality_controlled":"1","oa_version":"Preprint","volume":12826,"page":"486-515","main_file_link":[{"url":"https://eprint.iacr.org/2021/945","open_access":"1"}],"alternative_title":["LCNS"],"article_processing_charge":"No","publication":"41st Annual International Cryptology Conference, Part II ","project":[{"name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","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.","publisher":"Springer Nature","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","department":[{"_id":"KrPi"}],"status":"public","title":"Limits on the Adaptive Security of Yao’s Garbling"},{"quality_controlled":"1","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."}],"ec_funded":1,"author":[{"id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","last_name":"Kamath Hosdurg","first_name":"Chethan","full_name":"Kamath Hosdurg, Chethan"},{"id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","full_name":"Klein, Karen","first_name":"Karen","last_name":"Klein"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z"}],"citation":{"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.","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.","short":"C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, in:, 19th Theory of Cryptography Conference 2021, 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.","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.","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."},"related_material":{"record":[{"status":"public","relation":"later_version","id":"10409"},{"relation":"dissertation_contains","status":"public","id":"10035"}]},"oa":1,"day":"08","article_number":"2021/926","main_file_link":[{"url":"https://eprint.iacr.org/2021/926","open_access":"1"}],"date_published":"2021-07-08T00:00:00Z","conference":{"start_date":"2021-11-08","location":"Raleigh, NC, United States","name":"TCC: Theory of Cryptography Conference","end_date":"2021-11-11"},"_id":"10044","oa_version":"Preprint","date_created":"2021-09-24T12:01:34Z","project":[{"name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"682815"}],"year":"2021","acknowledgement":"We would like to thank Daniel Wichs for helpful discussions on the landscape of adaptive security of Yao’s garbling.  ","article_processing_charge":"No","language":[{"iso":"eng"}],"month":"07","publication":"19th Theory of Cryptography Conference 2021","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","status":"public","department":[{"_id":"KrPi"}],"title":"On treewidth, separators and Yao's garbling","publication_status":"published","date_updated":"2023-09-07T13:32:11Z","type":"conference","publisher":"International Association for Cryptologic Research"},{"date_published":"2021-07-08T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://ia.cr/2021/059"}],"date_created":"2021-09-27T12:52:05Z","oa_version":"Preprint","conference":{"end_date":"2021-11-11","name":"TCC: Theory of Cryptography Conference","location":"Raleigh, NC, United States","start_date":"2021-11-08"},"_id":"10048","author":[{"id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","last_name":"Kamath Hosdurg","first_name":"Chethan","full_name":"Kamath Hosdurg, Chethan"},{"full_name":"Klein, Karen","first_name":"Karen","last_name":"Klein","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","last_name":"Pietrzak","orcid":"0000-0002-9139-1654"},{"id":"488F98B0-F248-11E8-B48F-1D18A9856A87","first_name":"Michael","orcid":"0000-0003-3186-2482","last_name":"Walter","full_name":"Walter, Michael"}],"abstract":[{"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\r\nframework 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\r\nbounds 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\r\nbroadcast 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.\r\n","lang":"eng"}],"quality_controlled":"1","day":"08","oa":1,"related_material":{"record":[{"id":"10410","relation":"later_version","status":"public"},{"id":"10035","relation":"dissertation_contains","status":"public"}]},"citation":{"ieee":"C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and M. Walter, “The cost of adaptivity in security games on graphs,” in <i>19th Theory of Cryptography Conference 2021</i>, Raleigh, NC, United States, 2021.","chicago":"Kamath Hosdurg, Chethan, Karen Klein, Krzysztof Z Pietrzak, and Michael Walter. “The Cost of Adaptivity in Security Games on Graphs.” In <i>19th Theory of Cryptography Conference 2021</i>. International Association for Cryptologic Research, 2021.","short":"C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, M. Walter, in:, 19th Theory of Cryptography Conference 2021, International Association for Cryptologic Research, 2021.","ista":"Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. 2021. The cost of adaptivity in security games on graphs. 19th Theory of Cryptography Conference 2021. TCC: Theory of Cryptography Conference.","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 Theory of Cryptography Conference 2021</i>. Raleigh, NC, United States: International Association for Cryptologic Research.","ama":"Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. The cost of adaptivity in security games on graphs. In: <i>19th Theory of Cryptography Conference 2021</i>. International Association for Cryptologic Research; 2021.","mla":"Kamath Hosdurg, Chethan, et al. “The Cost of Adaptivity in Security Games on Graphs.” <i>19th Theory of Cryptography Conference 2021</i>, International Association for Cryptologic Research, 2021."},"publication_status":"published","title":"The cost of adaptivity in security games on graphs","status":"public","department":[{"_id":"KrPi"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"International Association for Cryptologic Research","type":"conference","date_updated":"2023-10-17T09:24:08Z","year":"2021","month":"07","publication":"19th Theory of Cryptography Conference 2021","language":[{"iso":"eng"}],"article_processing_charge":"No"},{"page":"268-284","oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2019/1489"}],"citation":{"apa":"Klein, K., Pascual Perez, G., Walter, M., Kamath Hosdurg, C., Capretto, M., Cueto Noval, M., … Pietrzak, K. Z. (2021). Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement. In <i>2021 IEEE Symposium on Security and Privacy </i> (pp. 268–284). San Francisco, CA, United States: IEEE. <a href=\"https://doi.org/10.1109/sp40001.2021.00035\">https://doi.org/10.1109/sp40001.2021.00035</a>","mla":"Klein, Karen, et al. “Keep the Dirt: Tainted TreeKEM, Adaptively and Actively Secure Continuous Group Key Agreement.” <i>2021 IEEE Symposium on Security and Privacy </i>, IEEE, 2021, pp. 268–84, doi:<a href=\"https://doi.org/10.1109/sp40001.2021.00035\">10.1109/sp40001.2021.00035</a>.","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.","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.","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>."},"oa":1,"day":"26","quality_controlled":"1","publisher":"IEEE","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","status":"public","title":"Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement","department":[{"_id":"KrPi"},{"_id":"DaAl"}],"article_processing_charge":"No","publication":"2021 IEEE Symposium on Security and Privacy ","project":[{"name":"International IST Doctoral Program","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","grant_number":"665385","call_identifier":"H2020"},{"name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"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.","_id":"10049","conference":{"end_date":"2021-05-27","name":"SP: Symposium on Security and Privacy","start_date":"2021-05-24","location":"San Francisco, CA, United States"},"date_created":"2021-09-27T13:46:27Z","date_published":"2021-08-26T00:00:00Z","related_material":{"record":[{"id":"10035","status":"public","relation":"dissertation_contains"}]},"author":[{"id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","first_name":"Karen","last_name":"Klein","full_name":"Klein, Karen"},{"full_name":"Pascual Perez, Guillermo","first_name":"Guillermo","orcid":"0000-0001-8630-415X","last_name":"Pascual Perez","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Walter","orcid":"0000-0003-3186-2482","first_name":"Michael","full_name":"Walter, Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Chethan","last_name":"Kamath Hosdurg","full_name":"Kamath Hosdurg, Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Capretto, Margarita","first_name":"Margarita","last_name":"Capretto"},{"id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","last_name":"Cueto Noval","first_name":"Miguel","full_name":"Cueto Noval, Miguel"},{"last_name":"Markov","first_name":"Ilia","full_name":"Markov, Ilia","id":"D0CF4148-C985-11E9-8066-0BDEE5697425"},{"full_name":"Yeo, Michelle X","last_name":"Yeo","first_name":"Michelle X","id":"2D82B818-F248-11E8-B48F-1D18A9856A87"},{"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","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"}],"ec_funded":1,"abstract":[{"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.","lang":"eng"}],"date_updated":"2023-09-07T13:32:11Z","type":"conference","publication_status":"published","language":[{"iso":"eng"}],"month":"08","year":"2021","doi":"10.1109/sp40001.2021.00035"},{"publication_status":"published","type":"conference","date_updated":"2023-08-17T06:21:38Z","doi":"10.1007/978-3-030-90453-1_17","year":"2021","month":"11","language":[{"iso":"eng"}],"date_published":"2021-11-04T00:00:00Z","scopus_import":"1","date_created":"2021-12-05T23:01:43Z","_id":"10409","conference":{"location":"Raleigh, NC, United States","start_date":"2021-11-08","end_date":"2021-11-11","name":"TCC: Theory of Cryptography"},"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   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."}],"author":[{"id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","first_name":"Chethan","last_name":"Kamath Hosdurg","full_name":"Kamath Hosdurg, Chethan"},{"last_name":"Klein","first_name":"Karen","full_name":"Klein, Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"}],"ec_funded":1,"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"10044"}]},"title":"On treewidth, separators and Yao’s garbling","status":"public","department":[{"_id":"KrPi"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publisher":"Springer Nature","external_id":{"isi":["000728364000017"]},"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.","project":[{"name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","call_identifier":"H2020"}],"publication":"19th International Conference","article_processing_charge":"No","main_file_link":[{"url":"https://eprint.iacr.org/2021/926","open_access":"1"}],"alternative_title":["LNCS"],"page":"486-517","oa_version":"Preprint","volume":"13043 ","isi":1,"quality_controlled":"1","publication_identifier":{"issn":["0302-9743"],"isbn":["9-783-0309-0452-4"],"eissn":["1611-3349"]},"day":"04","oa":1,"citation":{"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.","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>","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>.","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>","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>.","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.","short":"C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, in:, 19th International Conference, Springer Nature, 2021, pp. 486–517."}},{"main_file_link":[{"open_access":"1","url":"https://ia.cr/2021/059"}],"alternative_title":["LNCS"],"oa_version":"Preprint","volume":13043,"page":"550-581","isi":1,"quality_controlled":"1","publication_identifier":{"issn":["0302-9743"],"isbn":["9-783-0309-0452-4"],"eissn":["1611-3349"]},"day":"04","oa":1,"citation":{"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.","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>","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>.","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>","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>.","short":"C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, M. Walter, in:, 19th International Conference, Springer Nature, 2021, pp. 550–581."},"department":[{"_id":"KrPi"}],"title":"The cost of adaptivity in security games on graphs","status":"public","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publisher":"Springer Nature","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).","external_id":{"isi":["000728364000019"]},"project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"publication":"19th International Conference","article_processing_charge":"No","date_published":"2021-11-04T00:00:00Z","scopus_import":"1","date_created":"2021-12-05T23:01:43Z","_id":"10410","conference":{"end_date":"2021-11-11","name":"TCC: Theory of Cryptography","start_date":"2021-11-08","location":"Raleigh, NC, United States"},"abstract":[{"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.","lang":"eng"}],"ec_funded":1,"author":[{"id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","full_name":"Kamath Hosdurg, Chethan","last_name":"Kamath Hosdurg","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","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z"},{"last_name":"Walter","orcid":"0000-0003-3186-2482","first_name":"Michael","full_name":"Walter, Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87"}],"related_material":{"record":[{"id":"10048","relation":"earlier_version","status":"public"}]},"publication_status":"published","intvolume":"     13043","type":"conference","date_updated":"2023-10-17T09:24:07Z","doi":"10.1007/978-3-030-90453-1_19","year":"2021","month":"11","language":[{"iso":"eng"}]},{"project":[{"_id":"258C570E-B435-11E9-9278-68D0E5697425","grant_number":"259668","call_identifier":"FP7","name":"Provable Security for Physical Cryptography"},{"name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","call_identifier":"H2020"}],"article_processing_charge":"No","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","file_date_updated":"2020-07-14T12:48:04Z","has_accepted_license":"1","title":"On the average-case hardness of total search problems","status":"public","department":[{"_id":"KrPi"}],"publisher":"Institute of Science and Technology Austria","publication_identifier":{"issn":["2663-337X"]},"citation":{"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>.","short":"C. Kamath Hosdurg, On the Average-Case Hardness of Total Search Problems, Institute of Science and Technology Austria, 2020.","ista":"Kamath Hosdurg C. 2020. On the average-case hardness of total search problems. Institute of Science and Technology Austria.","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>","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>.","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>"},"oa":1,"day":"25","alternative_title":["ISTA Thesis"],"tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"oa_version":"Published Version","page":"126","file":[{"date_updated":"2020-07-14T12:48:04Z","date_created":"2020-05-26T14:08:13Z","checksum":"b39e2e1c376f5819b823fb7077491c64","access_level":"open_access","file_size":1622742,"file_id":"7897","creator":"dernst","content_type":"application/pdf","relation":"main_file","file_name":"2020_Thesis_Kamath.pdf"},{"file_name":"Thesis_Kamath.zip","content_type":"application/x-zip-compressed","relation":"source_file","file_id":"7898","creator":"dernst","file_size":15301529,"access_level":"closed","checksum":"8b26ba729c1a85ac6bea775f5d73cdc7","date_created":"2020-05-26T14:08:23Z","date_updated":"2020-07-14T12:48:04Z"}],"ddc":["000"],"year":"2020","doi":"10.15479/AT:ISTA:7896","language":[{"iso":"eng"}],"month":"05","publication_status":"published","date_updated":"2023-09-07T13:15:55Z","type":"dissertation","supervisor":[{"full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"}],"ec_funded":1,"author":[{"id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","full_name":"Kamath Hosdurg, Chethan","first_name":"Chethan","last_name":"Kamath Hosdurg"}],"abstract":[{"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. ","lang":"eng"}],"related_material":{"record":[{"id":"6677","status":"public","relation":"part_of_dissertation"}]},"license":"https://creativecommons.org/licenses/by/4.0/","date_published":"2020-05-25T00:00:00Z","_id":"7896","degree_awarded":"PhD","date_created":"2020-05-26T14:08:55Z"},{"publication_identifier":{"isbn":["9781450367059"]},"isi":1,"quality_controlled":"1","oa":1,"citation":{"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.","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.","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>.","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>.","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>","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."},"day":"01","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2019/549"}],"page":"1103-1114","oa_version":"Preprint","project":[{"grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks"}],"external_id":{"isi":["000523199100100"]},"article_processing_charge":"No","publication":"Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing  - STOC 2019","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","title":"Finding a Nash equilibrium is no easier than breaking Fiat-Shamir","status":"public","department":[{"_id":"KrPi"}],"publisher":"ACM Press","author":[{"last_name":"Choudhuri","first_name":"Arka Rai","full_name":"Choudhuri, Arka Rai"},{"full_name":"Hubáček, Pavel","last_name":"Hubáček","first_name":"Pavel"},{"full_name":"Kamath Hosdurg, Chethan","first_name":"Chethan","last_name":"Kamath Hosdurg","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Alon","last_name":"Rosen","full_name":"Rosen, Alon"},{"full_name":"Rothblum, Guy N.","first_name":"Guy N.","last_name":"Rothblum"}],"ec_funded":1,"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)."}],"related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"7896"}]},"date_published":"2019-06-01T00:00:00Z","scopus_import":"1","conference":{"end_date":"2019-06-26","name":"STOC: Symposium on Theory of Computing","start_date":"2019-06-23","location":"Phoenix, AZ, United States"},"_id":"6677","date_created":"2019-07-24T09:20:53Z","doi":"10.1145/3313276.3316400","year":"2019","language":[{"iso":"eng"}],"month":"06","publication_status":"published","type":"conference","date_updated":"2023-09-07T13:15:55Z"},{"alternative_title":["LNCS"],"main_file_link":[{"url":"https://eprint.iacr.org/2019/252","open_access":"1"}],"page":"277-291","volume":11477,"oa_version":"Submitted Version","quality_controlled":"1","isi":1,"publication_identifier":{"eissn":["1611-3349"],"isbn":["9783030176556","9783030176563"],"issn":["0302-9743"]},"day":"24","citation":{"ista":"Abusalah HM, Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. 2019. Reversible proofs of sequential work. Advances in Cryptology – EUROCRYPT 2019. International Conference on the Theory and Applications of Cryptographic Techniques, LNCS, vol. 11477, 277–291.","apa":"Abusalah, H. M., Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., &#38; Walter, M. (2019). Reversible proofs of sequential work. In <i>Advances in Cryptology – EUROCRYPT 2019</i> (Vol. 11477, pp. 277–291). Darmstadt, Germany: Springer International Publishing. <a href=\"https://doi.org/10.1007/978-3-030-17656-3_10\">https://doi.org/10.1007/978-3-030-17656-3_10</a>","mla":"Abusalah, Hamza M., et al. “Reversible Proofs of Sequential Work.” <i>Advances in Cryptology – EUROCRYPT 2019</i>, vol. 11477, Springer International Publishing, 2019, pp. 277–91, doi:<a href=\"https://doi.org/10.1007/978-3-030-17656-3_10\">10.1007/978-3-030-17656-3_10</a>.","ama":"Abusalah HM, Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. Reversible proofs of sequential work. In: <i>Advances in Cryptology – EUROCRYPT 2019</i>. Vol 11477. Springer International Publishing; 2019:277-291. doi:<a href=\"https://doi.org/10.1007/978-3-030-17656-3_10\">10.1007/978-3-030-17656-3_10</a>","chicago":"Abusalah, Hamza M, Chethan Kamath Hosdurg, Karen Klein, Krzysztof Z Pietrzak, and Michael Walter. “Reversible Proofs of Sequential Work.” In <i>Advances in Cryptology – EUROCRYPT 2019</i>, 11477:277–91. Springer International Publishing, 2019. <a href=\"https://doi.org/10.1007/978-3-030-17656-3_10\">https://doi.org/10.1007/978-3-030-17656-3_10</a>.","ieee":"H. M. Abusalah, C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and M. Walter, “Reversible proofs of sequential work,” in <i>Advances in Cryptology – EUROCRYPT 2019</i>, Darmstadt, Germany, 2019, vol. 11477, pp. 277–291.","short":"H.M. Abusalah, C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, M. Walter, in:, Advances in Cryptology – EUROCRYPT 2019, Springer International Publishing, 2019, pp. 277–291."},"oa":1,"department":[{"_id":"KrPi"}],"status":"public","title":"Reversible proofs of sequential work","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publisher":"Springer International Publishing","external_id":{"isi":["000483516200010"]},"project":[{"name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"publication":"Advances in Cryptology – EUROCRYPT 2019","article_processing_charge":"No","scopus_import":"1","date_published":"2019-04-24T00:00:00Z","date_created":"2020-01-30T09:26:14Z","conference":{"location":"Darmstadt, Germany","start_date":"2019-05-19","name":"International Conference on the Theory and Applications of Cryptographic Techniques","end_date":"2019-05-23"},"_id":"7411","author":[{"id":"40297222-F248-11E8-B48F-1D18A9856A87","last_name":"Abusalah","first_name":"Hamza M","full_name":"Abusalah, Hamza M"},{"last_name":"Kamath Hosdurg","first_name":"Chethan","full_name":"Kamath Hosdurg, Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Klein, Karen","last_name":"Klein","first_name":"Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z"},{"id":"488F98B0-F248-11E8-B48F-1D18A9856A87","full_name":"Walter, Michael","first_name":"Michael","last_name":"Walter","orcid":"0000-0003-3186-2482"}],"ec_funded":1,"abstract":[{"lang":"eng","text":"Proofs of sequential work (PoSW) are proof systems where a prover, upon receiving a statement χ and a time parameter T computes a proof ϕ(χ,T) which is efficiently and publicly verifiable. The proof can be computed in T sequential steps, but not much less, even by a malicious party having large parallelism. A PoSW thus serves as a proof that T units of time have passed since χ\r\n\r\nwas received.\r\n\r\nPoSW were introduced by Mahmoody, Moran and Vadhan [MMV11], a simple and practical construction was only recently proposed by Cohen and Pietrzak [CP18].\r\n\r\nIn this work we construct a new simple PoSW in the random permutation model which is almost as simple and efficient as [CP18] but conceptually very different. Whereas the structure underlying [CP18] is a hash tree, our construction is based on skip lists and has the interesting property that computing the PoSW is a reversible computation.\r\nThe fact that the construction is reversible can potentially be used for new applications like constructing proofs of replication. We also show how to “embed” the sloth function of Lenstra and Weselowski [LW17] into our PoSW to get a PoSW where one additionally can verify correctness of the output much more efficiently than recomputing it (though recent constructions of “verifiable delay functions” subsume most of the applications this construction was aiming at)."}],"intvolume":"     11477","publication_status":"published","date_updated":"2023-09-06T15:26:06Z","type":"conference","year":"2019","doi":"10.1007/978-3-030-17656-3_10","month":"04","language":[{"iso":"eng"}]},{"publication_status":"published","intvolume":"     11443","type":"conference","date_updated":"2023-09-08T11:33:20Z","doi":"10.1007/978-3-030-17259-6_11","year":"2019","month":"04","language":[{"iso":"eng"}],"date_published":"2019-04-06T00:00:00Z","scopus_import":"1","date_created":"2019-05-13T08:13:46Z","conference":{"end_date":"2019-04-17","name":"PKC: Public-Key Cryptograhy","location":"Beijing, China","start_date":"2019-04-14"},"_id":"6430","abstract":[{"text":"A proxy re-encryption (PRE) scheme is a public-key encryption scheme that allows the holder of a key pk to derive a re-encryption key for any other key 𝑝𝑘′. This re-encryption key lets anyone transform ciphertexts under pk into ciphertexts under 𝑝𝑘′ without having to know the underlying message, while transformations from 𝑝𝑘′ to pk should not be possible (unidirectional). Security is defined in a multi-user setting against an adversary that gets the users’ public keys and can ask for re-encryption keys and can corrupt users by requesting their secret keys. Any ciphertext that the adversary cannot trivially decrypt given the obtained secret and re-encryption keys should be secure.\r\n\r\nAll existing security proofs for PRE only show selective security, where the adversary must first declare the users it wants to corrupt. This can be lifted to more meaningful adaptive security by guessing the set of corrupted users among the n users, which loses a factor exponential in  Open image in new window , rendering the result meaningless already for moderate Open image in new window .\r\n\r\nJafargholi et al. (CRYPTO’17) proposed a framework that in some cases allows to give adaptive security proofs for schemes which were previously only known to be selectively secure, while avoiding the exponential loss that results from guessing the adaptive choices made by an adversary. We apply their framework to PREs that satisfy some natural additional properties. Concretely, we give a more fine-grained reduction for several unidirectional PREs, proving adaptive security at a much smaller loss. The loss depends on the graph of users whose edges represent the re-encryption keys queried by the adversary. For trees and chains the loss is quasi-polynomial in the size and for general graphs it is exponential in their depth and indegree (instead of their size as for previous reductions). Fortunately, trees and low-depth graphs cover many, if not most, interesting applications.\r\n\r\nOur results apply e.g. to the bilinear-map based PRE schemes by Ateniese et al. (NDSS’05 and CT-RSA’09), Gentry’s FHE-based scheme (STOC’09) and the LWE-based scheme by Chandran et al. (PKC’14).","lang":"eng"}],"ec_funded":1,"author":[{"id":"46B4C3EE-F248-11E8-B48F-1D18A9856A87","last_name":"Fuchsbauer","first_name":"Georg","full_name":"Fuchsbauer, Georg"},{"full_name":"Kamath Hosdurg, Chethan","first_name":"Chethan","last_name":"Kamath Hosdurg","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87"},{"id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","full_name":"Klein, Karen","last_name":"Klein","first_name":"Karen"},{"full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"}],"related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"10035"}]},"status":"public","title":"Adaptively secure proxy re-encryption","department":[{"_id":"KrPi"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publisher":"Springer Nature","project":[{"call_identifier":"H2020","grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks"}],"article_processing_charge":"No","main_file_link":[{"url":"https://eprint.iacr.org/2018/426","open_access":"1"}],"alternative_title":["LNCS"],"page":"317-346","oa_version":"Preprint","volume":11443,"quality_controlled":"1","publication_identifier":{"issn":["03029743"],"eissn":["16113349"],"isbn":["9783030172589"]},"day":"06","oa":1,"citation":{"apa":"Fuchsbauer, G., Kamath Hosdurg, C., Klein, K., &#38; Pietrzak, K. Z. (2019). Adaptively secure proxy re-encryption (Vol. 11443, pp. 317–346). Presented at the PKC: Public-Key Cryptograhy, Beijing, China: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-17259-6_11\">https://doi.org/10.1007/978-3-030-17259-6_11</a>","mla":"Fuchsbauer, Georg, et al. <i>Adaptively Secure Proxy Re-Encryption</i>. Vol. 11443, Springer Nature, 2019, pp. 317–46, doi:<a href=\"https://doi.org/10.1007/978-3-030-17259-6_11\">10.1007/978-3-030-17259-6_11</a>.","ama":"Fuchsbauer G, Kamath Hosdurg C, Klein K, Pietrzak KZ. Adaptively secure proxy re-encryption. In: Vol 11443. Springer Nature; 2019:317-346. doi:<a href=\"https://doi.org/10.1007/978-3-030-17259-6_11\">10.1007/978-3-030-17259-6_11</a>","ista":"Fuchsbauer G, Kamath Hosdurg C, Klein K, Pietrzak KZ. 2019. Adaptively secure proxy re-encryption. PKC: Public-Key Cryptograhy, LNCS, vol. 11443, 317–346.","short":"G. Fuchsbauer, C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, in:, Springer Nature, 2019, pp. 317–346.","chicago":"Fuchsbauer, Georg, Chethan Kamath Hosdurg, Karen Klein, and Krzysztof Z Pietrzak. “Adaptively Secure Proxy Re-Encryption,” 11443:317–46. Springer Nature, 2019. <a href=\"https://doi.org/10.1007/978-3-030-17259-6_11\">https://doi.org/10.1007/978-3-030-17259-6_11</a>.","ieee":"G. Fuchsbauer, C. Kamath Hosdurg, K. Klein, and K. Z. Pietrzak, “Adaptively secure proxy re-encryption,” presented at the PKC: Public-Key Cryptograhy, Beijing, China, 2019, vol. 11443, pp. 317–346."}},{"oa":1,"citation":{"short":"J.F. Alwen, P. Gazi, C. Kamath Hosdurg, K. Klein, G.F. Osang, K.Z. Pietrzak, L. Reyzin, M. Rolinek, M. Rybar, in:, Proceedings of the 2018 on Asia Conference on Computer and Communication Security, ACM, 2018, pp. 51–65.","ieee":"J. F. Alwen <i>et al.</i>, “On the memory hardness of data independent password hashing functions,” in <i>Proceedings of the 2018 on Asia Conference on Computer and Communication Security</i>, Incheon, Republic of Korea, 2018, pp. 51–65.","chicago":"Alwen, Joel F, Peter Gazi, Chethan Kamath Hosdurg, Karen Klein, Georg F Osang, Krzysztof Z Pietrzak, Lenoid Reyzin, Michal Rolinek, and Michal Rybar. “On the Memory Hardness of Data Independent Password Hashing Functions.” In <i>Proceedings of the 2018 on Asia Conference on Computer and Communication Security</i>, 51–65. ACM, 2018. <a href=\"https://doi.org/10.1145/3196494.3196534\">https://doi.org/10.1145/3196494.3196534</a>.","ama":"Alwen JF, Gazi P, Kamath Hosdurg C, et al. On the memory hardness of data independent password hashing functions. In: <i>Proceedings of the 2018 on Asia Conference on Computer and Communication Security</i>. ACM; 2018:51-65. doi:<a href=\"https://doi.org/10.1145/3196494.3196534\">10.1145/3196494.3196534</a>","mla":"Alwen, Joel F., et al. “On the Memory Hardness of Data Independent Password Hashing Functions.” <i>Proceedings of the 2018 on Asia Conference on Computer and Communication Security</i>, ACM, 2018, pp. 51–65, doi:<a href=\"https://doi.org/10.1145/3196494.3196534\">10.1145/3196494.3196534</a>.","apa":"Alwen, J. F., Gazi, P., Kamath Hosdurg, C., Klein, K., Osang, G. F., Pietrzak, K. Z., … Rybar, M. (2018). On the memory hardness of data independent password hashing functions. In <i>Proceedings of the 2018 on Asia Conference on Computer and Communication Security</i> (pp. 51–65). Incheon, Republic of Korea: ACM. <a href=\"https://doi.org/10.1145/3196494.3196534\">https://doi.org/10.1145/3196494.3196534</a>","ista":"Alwen JF, Gazi P, Kamath Hosdurg C, Klein K, Osang GF, Pietrzak KZ, Reyzin L, Rolinek M, Rybar M. 2018. On the memory hardness of data independent password hashing functions. Proceedings of the 2018 on Asia Conference on Computer and Communication Security. ASIACCS: Asia Conference on Computer and Communications Security , 51–65."},"day":"01","isi":1,"quality_controlled":"1","page":"51 - 65","oa_version":"Submitted Version","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2016/783"}],"article_processing_charge":"No","publication":"Proceedings of the 2018 on Asia Conference on Computer and Communication Security","project":[{"name":"Discrete Optimization in Computer Vision: Theory and Practice","_id":"25FBA906-B435-11E9-9278-68D0E5697425","grant_number":"616160","call_identifier":"FP7"},{"name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"acknowledgement":"Leonid Reyzin was supported in part by IST Austria and by US NSF grants 1012910, 1012798, and 1422965; this research was performed while he was visiting IST Austria.","external_id":{"isi":["000516620100005"]},"publist_id":"7723","publisher":"ACM","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","department":[{"_id":"KrPi"},{"_id":"HeEd"},{"_id":"VlKo"}],"title":"On the memory hardness of data independent password hashing functions","status":"public","ec_funded":1,"author":[{"id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","full_name":"Alwen, Joel F","last_name":"Alwen","first_name":"Joel F"},{"last_name":"Gazi","first_name":"Peter","full_name":"Gazi, Peter"},{"last_name":"Kamath Hosdurg","first_name":"Chethan","full_name":"Kamath Hosdurg, Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87"},{"id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","last_name":"Klein","first_name":"Karen","full_name":"Klein, Karen"},{"id":"464B40D6-F248-11E8-B48F-1D18A9856A87","full_name":"Osang, Georg F","first_name":"Georg F","orcid":"0000-0002-8882-5116","last_name":"Osang"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","first_name":"Krzysztof Z"},{"full_name":"Reyzin, Lenoid","last_name":"Reyzin","first_name":"Lenoid"},{"id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","full_name":"Rolinek, Michal","first_name":"Michal","last_name":"Rolinek"},{"id":"2B3E3DE8-F248-11E8-B48F-1D18A9856A87","full_name":"Rybar, Michal","last_name":"Rybar","first_name":"Michal"}],"abstract":[{"text":"We show attacks on five data-independent memory-hard functions (iMHF) that were submitted to the password hashing competition (PHC). Informally, an MHF is a function which cannot be evaluated on dedicated hardware, like ASICs, at significantly lower hardware and/or energy cost than evaluating a single instance on a standard single-core architecture. Data-independent means the memory access pattern of the function is independent of the input; this makes iMHFs harder to construct than data-dependent ones, but the latter can be attacked by various side-channel attacks. Following [Alwen-Blocki'16], we capture the evaluation of an iMHF as a directed acyclic graph (DAG). The cumulative parallel pebbling complexity of this DAG is a measure for the hardware cost of evaluating the iMHF on an ASIC. Ideally, one would like the complexity of a DAG underlying an iMHF to be as close to quadratic in the number of nodes of the graph as possible. Instead, we show that (the DAGs underlying) the following iMHFs are far from this bound: Rig.v2, TwoCats and Gambit each having an exponent no more than 1.75. Moreover, we show that the complexity of the iMHF modes of the PHC finalists Pomelo and Lyra2 have exponents at most 1.83 and 1.67 respectively. To show this we investigate a combinatorial property of each underlying DAG (called its depth-robustness. By establishing upper bounds on this property we are then able to apply the general technique of [Alwen-Block'16] for analyzing the hardware costs of an iMHF.","lang":"eng"}],"conference":{"name":"ASIACCS: Asia Conference on Computer and Communications Security ","end_date":"2018-06-08","location":"Incheon, Republic of Korea","start_date":"2018-06-04"},"_id":"193","date_created":"2018-12-11T11:45:07Z","date_published":"2018-06-01T00:00:00Z","scopus_import":"1","language":[{"iso":"eng"}],"month":"06","doi":"10.1145/3196494.3196534","year":"2018","type":"conference","date_updated":"2023-09-13T09:13:12Z","publication_status":"published"},{"author":[{"first_name":"Sanjit","last_name":"Chatterjee","full_name":"Chatterjee, Sanjit"},{"full_name":"Kamath Hosdurg, Chethan","last_name":"Kamath Hosdurg","first_name":"Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Kumar, Vikas","last_name":"Kumar","first_name":"Vikas"}],"quality_controlled":"1","abstract":[{"lang":"eng","text":"The problem of private set-intersection (PSI) has been traditionally treated as an instance of the more general problem of multi-party computation (MPC). Consequently, in order to argue security, or compose these protocols one has to rely on the general theory that was developed for the purpose of MPC. The pursuit of efficient protocols, however, has resulted in designs that exploit properties pertaining to PSI. In almost all practical applications where a PSI protocol is deployed, it is expected to be executed multiple times, possibly on related inputs. In this work we initiate a dedicated study of PSI in the multi-interaction (MI) setting. In this model a server sets up the common system parameters and executes set-intersection multiple times with potentially different clients. We discuss a few attacks that arise when protocols are naïvely composed in this manner and, accordingly, craft security definitions for the MI setting and study their inter-relation. Finally, we suggest a set of protocols that are MI-secure, at the same time almost as efficient as their parent, stand-alone, protocols."}],"isi":1,"issue":"1","day":"01","citation":{"short":"S. Chatterjee, C. Kamath Hosdurg, V. Kumar, American Institute of Mathematical Sciences 12 (2018) 17–47.","ieee":"S. Chatterjee, C. Kamath Hosdurg, and V. Kumar, “Private set-intersection with common set-up,” <i>American Institute of Mathematical Sciences</i>, vol. 12, no. 1. AIMS, pp. 17–47, 2018.","chicago":"Chatterjee, Sanjit, Chethan Kamath Hosdurg, and Vikas Kumar. “Private Set-Intersection with Common Set-Up.” <i>American Institute of Mathematical Sciences</i>. AIMS, 2018. <a href=\"https://doi.org/10.3934/amc.2018002\">https://doi.org/10.3934/amc.2018002</a>.","ama":"Chatterjee S, Kamath Hosdurg C, Kumar V. Private set-intersection with common set-up. <i>American Institute of Mathematical Sciences</i>. 2018;12(1):17-47. doi:<a href=\"https://doi.org/10.3934/amc.2018002\">10.3934/amc.2018002</a>","mla":"Chatterjee, Sanjit, et al. “Private Set-Intersection with Common Set-Up.” <i>American Institute of Mathematical Sciences</i>, vol. 12, no. 1, AIMS, 2018, pp. 17–47, doi:<a href=\"https://doi.org/10.3934/amc.2018002\">10.3934/amc.2018002</a>.","apa":"Chatterjee, S., Kamath Hosdurg, C., &#38; Kumar, V. (2018). Private set-intersection with common set-up. <i>American Institute of Mathematical Sciences</i>. AIMS. <a href=\"https://doi.org/10.3934/amc.2018002\">https://doi.org/10.3934/amc.2018002</a>","ista":"Chatterjee S, Kamath Hosdurg C, Kumar V. 2018. Private set-intersection with common set-up. American Institute of Mathematical Sciences. 12(1), 17–47."},"scopus_import":"1","date_published":"2018-02-01T00:00:00Z","date_created":"2019-02-13T13:49:41Z","_id":"5980","page":"17-47","oa_version":"None","volume":12,"year":"2018","doi":"10.3934/amc.2018002","external_id":{"isi":["000430950400002"]},"month":"02","publication":"American Institute of Mathematical Sciences","article_processing_charge":"No","language":[{"iso":"eng"}],"department":[{"_id":"KrPi"}],"title":"Private set-intersection with common set-up","status":"public","intvolume":"        12","publication_status":"published","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publisher":"AIMS","date_updated":"2023-09-19T14:27:59Z","type":"journal_article"},{"related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"10035"}]},"ec_funded":1,"author":[{"full_name":"Jafargholi, Zahra","last_name":"Jafargholi","first_name":"Zahra"},{"id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","full_name":"Kamath Hosdurg, Chethan","last_name":"Kamath Hosdurg","first_name":"Chethan"},{"first_name":"Karen","last_name":"Klein","full_name":"Klein, Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Komargodski, Ilan","first_name":"Ilan","last_name":"Komargodski"},{"first_name":"Krzysztof Z","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Wichs, Daniel","last_name":"Wichs","first_name":"Daniel"}],"abstract":[{"text":"For many cryptographic primitives, it is relatively easy to achieve selective security (where the adversary commits a-priori to some of the choices to be made later in the attack) but appears difficult to achieve the more natural notion of adaptive security (where the adversary can make all choices on the go as the attack progresses). A series of several recent works shows how to cleverly achieve adaptive security in several such scenarios including generalized selective decryption (Panjwani, TCC ’07 and Fuchsbauer et al., CRYPTO ’15), constrained PRFs (Fuchsbauer et al., ASIACRYPT ’14), and Yao garbled circuits (Jafargholi and Wichs, TCC ’16b). 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 that connects all of these works and allows us to present them in a unified and simplified fashion. Moreover, we use the framework to derive a new result for adaptively secure secret sharing over access structures defined via monotone circuits. We envision that further applications will follow in the future. Underlying our framework is the following simple idea. It is well known that selective security, where the adversary commits to n-bits of information about his future choices, automatically implies adaptive security at the cost of amplifying the adversary’s advantage by a factor of up to 2n. However, in some cases the proof of selective security proceeds via a sequence of hybrids, where each pair of adjacent hybrids locally only requires some smaller partial information consisting of m ≪ n bits. The partial information needed might be completely different between different pairs of hybrids, and if we look across all the hybrids we might rely on the entire n-bit commitment. Nevertheless, the above is sufficient to prove adaptive security, at the cost of amplifying the adversary’s advantage by a factor of only 2m ≪ 2n. In all of our examples using the above framework, the different hybrids are captured by some sort of a graph pebbling game and the amount of information that the adversary needs to commit to in each pair of hybrids is bounded by the maximum number of pebbles in play at any point in time. Therefore, coming up with better strategies for proving adaptive security translates to various pebbling strategies for different types of graphs.","lang":"eng"}],"date_created":"2018-12-11T11:47:38Z","_id":"637","conference":{"end_date":"2017-07-24","name":"CRYPTO: Cryptology","location":"Santa Barbara, CA, United States","start_date":"2017-07-20"},"editor":[{"full_name":"Katz, Jonathan","first_name":"Jonathan","last_name":"Katz"},{"first_name":"Hovav","last_name":"Shacham","full_name":"Shacham, Hovav"}],"date_published":"2017-01-01T00:00:00Z","scopus_import":1,"month":"01","language":[{"iso":"eng"}],"doi":"10.1007/978-3-319-63688-7_5","year":"2017","type":"conference","date_updated":"2023-09-07T13:32:11Z","publication_status":"published","intvolume":"     10401","day":"01","oa":1,"citation":{"ista":"Jafargholi Z, Kamath Hosdurg C, Klein K, Komargodski I, Pietrzak KZ, Wichs D. 2017. Be adaptive avoid overcommitting. CRYPTO: Cryptology, LNCS, vol. 10401, 133–163.","apa":"Jafargholi, Z., Kamath Hosdurg, C., Klein, K., Komargodski, I., Pietrzak, K. Z., &#38; Wichs, D. (2017). Be adaptive avoid overcommitting. In J. Katz &#38; H. Shacham (Eds.) (Vol. 10401, pp. 133–163). Presented at the CRYPTO: Cryptology, Santa Barbara, CA, United States: Springer. <a href=\"https://doi.org/10.1007/978-3-319-63688-7_5\">https://doi.org/10.1007/978-3-319-63688-7_5</a>","ama":"Jafargholi Z, Kamath Hosdurg C, Klein K, Komargodski I, Pietrzak KZ, Wichs D. Be adaptive avoid overcommitting. In: Katz J, Shacham H, eds. Vol 10401. Springer; 2017:133-163. doi:<a href=\"https://doi.org/10.1007/978-3-319-63688-7_5\">10.1007/978-3-319-63688-7_5</a>","mla":"Jafargholi, Zahra, et al. <i>Be Adaptive Avoid Overcommitting</i>. Edited by Jonathan Katz and Hovav Shacham, vol. 10401, Springer, 2017, pp. 133–63, doi:<a href=\"https://doi.org/10.1007/978-3-319-63688-7_5\">10.1007/978-3-319-63688-7_5</a>.","chicago":"Jafargholi, Zahra, Chethan Kamath Hosdurg, Karen Klein, Ilan Komargodski, Krzysztof Z Pietrzak, and Daniel Wichs. “Be Adaptive Avoid Overcommitting.” edited by Jonathan Katz and Hovav Shacham, 10401:133–63. Springer, 2017. <a href=\"https://doi.org/10.1007/978-3-319-63688-7_5\">https://doi.org/10.1007/978-3-319-63688-7_5</a>.","ieee":"Z. Jafargholi, C. Kamath Hosdurg, K. Klein, I. Komargodski, K. Z. Pietrzak, and D. Wichs, “Be adaptive avoid overcommitting,” presented at the CRYPTO: Cryptology, Santa Barbara, CA, United States, 2017, vol. 10401, pp. 133–163.","short":"Z. Jafargholi, C. Kamath Hosdurg, K. Klein, I. Komargodski, K.Z. Pietrzak, D. Wichs, in:, J. Katz, H. Shacham (Eds.), Springer, 2017, pp. 133–163."},"quality_controlled":"1","publication_identifier":{"isbn":["978-331963687-0"]},"volume":10401,"page":"133 - 163","oa_version":"Submitted Version","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2017/515"}],"alternative_title":["LNCS"],"publist_id":"7151","project":[{"name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"682815"}],"publisher":"Springer","title":"Be adaptive avoid overcommitting","status":"public","department":[{"_id":"KrPi"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87"},{"doi":"10.1007/s00453-015-9997-6","acknowledgement":"We are grateful to the anonymous reviewers for their insightful comments. The\r\ndetailed reports helped us a lot to address the technical mistakes as well as to improve the overall presentation of the paper.","year":"2016","publist_id":"6177","month":"04","publication":"Algorithmica","language":[{"iso":"eng"}],"publication_status":"published","intvolume":"        74","status":"public","department":[{"_id":"KrPi"}],"title":"A closer look at multiple-forking: Leveraging (in)dependence for a tighter bound","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publisher":"Springer","type":"journal_article","date_updated":"2021-01-12T06:48:52Z","author":[{"full_name":"Kamath Hosdurg, Chethan","first_name":"Chethan","last_name":"Kamath Hosdurg","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Chatterjee","first_name":"Sanjit","full_name":"Chatterjee, Sanjit"}],"abstract":[{"text":"Boldyreva, Palacio and Warinschi introduced a multiple forking game as an extension of general forking. The notion of (multiple) forking is a useful abstraction from the actual simulation of cryptographic scheme to the adversary in a security reduction, and is achieved through the intermediary of a so-called wrapper algorithm. Multiple forking has turned out to be a useful tool in the security argument of several cryptographic protocols. However, a reduction employing multiple forking incurs a significant degradation of (Formula presented.) , where (Formula presented.) denotes the upper bound on the underlying random oracle calls and (Formula presented.) , the number of forkings. In this work we take a closer look at the reasons for the degradation with a tighter security bound in mind. We nail down the exact set of conditions for success in the multiple forking game. A careful analysis of the cryptographic schemes and corresponding security reduction employing multiple forking leads to the formulation of ‘dependence’ and ‘independence’ conditions pertaining to the output of the wrapper in different rounds. Based on the (in)dependence conditions we propose a general framework of multiple forking and a General Multiple Forking Lemma. Leveraging (in)dependence to the full allows us to improve the degradation factor in the multiple forking game by a factor of (Formula presented.). By implication, the cost of a single forking involving two random oracles (augmented forking) matches that involving a single random oracle (elementary forking). Finally, we study the effect of these observations on the concrete security of existing schemes employing multiple forking. We conclude that by careful design of the protocol (and the wrapper in the security reduction) it is possible to harness our observations to the full extent.","lang":"eng"}],"quality_controlled":"1","issue":"4","day":"01","oa":1,"citation":{"ama":"Kamath Hosdurg C, Chatterjee S. A closer look at multiple-forking: Leveraging (in)dependence for a tighter bound. <i>Algorithmica</i>. 2016;74(4):1321-1362. doi:<a href=\"https://doi.org/10.1007/s00453-015-9997-6\">10.1007/s00453-015-9997-6</a>","mla":"Kamath Hosdurg, Chethan, and Sanjit Chatterjee. “A Closer Look at Multiple-Forking: Leveraging (in)Dependence for a Tighter Bound.” <i>Algorithmica</i>, vol. 74, no. 4, Springer, 2016, pp. 1321–62, doi:<a href=\"https://doi.org/10.1007/s00453-015-9997-6\">10.1007/s00453-015-9997-6</a>.","apa":"Kamath Hosdurg, C., &#38; Chatterjee, S. (2016). A closer look at multiple-forking: Leveraging (in)dependence for a tighter bound. <i>Algorithmica</i>. Springer. <a href=\"https://doi.org/10.1007/s00453-015-9997-6\">https://doi.org/10.1007/s00453-015-9997-6</a>","ista":"Kamath Hosdurg C, Chatterjee S. 2016. A closer look at multiple-forking: Leveraging (in)dependence for a tighter bound. Algorithmica. 74(4), 1321–1362.","short":"C. Kamath Hosdurg, S. Chatterjee, Algorithmica 74 (2016) 1321–1362.","ieee":"C. Kamath Hosdurg and S. Chatterjee, “A closer look at multiple-forking: Leveraging (in)dependence for a tighter bound,” <i>Algorithmica</i>, vol. 74, no. 4. Springer, pp. 1321–1362, 2016.","chicago":"Kamath Hosdurg, Chethan, and Sanjit Chatterjee. “A Closer Look at Multiple-Forking: Leveraging (in)Dependence for a Tighter Bound.” <i>Algorithmica</i>. Springer, 2016. <a href=\"https://doi.org/10.1007/s00453-015-9997-6\">https://doi.org/10.1007/s00453-015-9997-6</a>."},"date_published":"2016-04-01T00:00:00Z","main_file_link":[{"open_access":"1","url":"http://eprint.iacr.org/2013/651"}],"date_created":"2018-12-11T11:50:33Z","page":"1321 - 1362","oa_version":"Submitted Version","volume":74,"_id":"1177"},{"publication_status":"published","intvolume":"      9841","type":"conference","date_updated":"2023-02-23T10:08:16Z","doi":"10.1007/978-3-319-44618-9_21","year":"2016","language":[{"iso":"eng"}],"month":"08","date_published":"2016-08-11T00:00:00Z","scopus_import":1,"_id":"1225","conference":{"end_date":"2016-09-02","name":"SCN: Security and Cryptography for Networks","start_date":"2016-08-31","location":"Amalfi, Italy"},"date_created":"2018-12-11T11:50:49Z","abstract":[{"text":"At Crypto 2015 Fuchsbauer, Hanser and Slamanig (FHS) presented the first standard-model construction of efficient roundoptimal blind signatures that does not require complexity leveraging. It is conceptually simple and builds on the primitive of structure-preserving signatures on equivalence classes (SPS-EQ). FHS prove the unforgeability of their scheme assuming EUF-CMA security of the SPS-EQ scheme and hardness of a version of the DH inversion problem. Blindness under adversarially chosen keys is proven under an interactive variant of the DDH assumption. We propose a variant of their scheme whose blindness can be proven under a non-interactive assumption, namely a variant of the bilinear DDH assumption. We moreover prove its unforgeability assuming only unforgeability of the underlying SPS-EQ but no additional assumptions as needed for the FHS scheme.","lang":"eng"}],"ec_funded":1,"author":[{"full_name":"Fuchsbauer, Georg","last_name":"Fuchsbauer","first_name":"Georg","id":"46B4C3EE-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Hanser","first_name":"Christian","full_name":"Hanser, Christian"},{"id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","first_name":"Chethan","last_name":"Kamath Hosdurg","full_name":"Kamath Hosdurg, Chethan"},{"last_name":"Slamanig","first_name":"Daniel","full_name":"Slamanig, Daniel"}],"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"1647"}]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Practical round-optimal blind signatures in the standard model from weaker assumptions","status":"public","department":[{"_id":"KrPi"}],"publisher":"Springer","project":[{"_id":"258C570E-B435-11E9-9278-68D0E5697425","grant_number":"259668","call_identifier":"FP7","name":"Provable Security for Physical Cryptography"},{"name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"682815"}],"publist_id":"6109","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2016/662"}],"alternative_title":["LNCS"],"page":"391 - 408","volume":9841,"oa_version":"Submitted Version","quality_controlled":"1","oa":1,"citation":{"mla":"Fuchsbauer, Georg, et al. <i>Practical Round-Optimal Blind Signatures in the Standard Model from Weaker Assumptions</i>. Vol. 9841, Springer, 2016, pp. 391–408, doi:<a href=\"https://doi.org/10.1007/978-3-319-44618-9_21\">10.1007/978-3-319-44618-9_21</a>.","ama":"Fuchsbauer G, Hanser C, Kamath Hosdurg C, Slamanig D. Practical round-optimal blind signatures in the standard model from weaker assumptions. In: Vol 9841. Springer; 2016:391-408. doi:<a href=\"https://doi.org/10.1007/978-3-319-44618-9_21\">10.1007/978-3-319-44618-9_21</a>","apa":"Fuchsbauer, G., Hanser, C., Kamath Hosdurg, C., &#38; Slamanig, D. (2016). Practical round-optimal blind signatures in the standard model from weaker assumptions (Vol. 9841, pp. 391–408). Presented at the SCN: Security and Cryptography for Networks, Amalfi, Italy: Springer. <a href=\"https://doi.org/10.1007/978-3-319-44618-9_21\">https://doi.org/10.1007/978-3-319-44618-9_21</a>","ista":"Fuchsbauer G, Hanser C, Kamath Hosdurg C, Slamanig D. 2016. Practical round-optimal blind signatures in the standard model from weaker assumptions. SCN: Security and Cryptography for Networks, LNCS, vol. 9841, 391–408.","short":"G. Fuchsbauer, C. Hanser, C. Kamath Hosdurg, D. Slamanig, in:, Springer, 2016, pp. 391–408.","ieee":"G. Fuchsbauer, C. Hanser, C. Kamath Hosdurg, and D. Slamanig, “Practical round-optimal blind signatures in the standard model from weaker assumptions,” presented at the SCN: Security and Cryptography for Networks, Amalfi, Italy, 2016, vol. 9841, pp. 391–408.","chicago":"Fuchsbauer, Georg, Christian Hanser, Chethan Kamath Hosdurg, and Daniel Slamanig. “Practical Round-Optimal Blind Signatures in the Standard Model from Weaker Assumptions,” 9841:391–408. Springer, 2016. <a href=\"https://doi.org/10.1007/978-3-319-44618-9_21\">https://doi.org/10.1007/978-3-319-44618-9_21</a>."},"day":"11"},{"day":"28","citation":{"short":"J.F. Alwen, B. Chen, C. Kamath Hosdurg, V. Kolmogorov, K.Z. Pietrzak, S. Tessaro, in:, Springer, 2016, pp. 358–387.","chicago":"Alwen, Joel F, Binyi Chen, Chethan Kamath Hosdurg, Vladimir Kolmogorov, Krzysztof Z Pietrzak, and Stefano Tessaro. “On the Complexity of Scrypt and Proofs of Space in the Parallel Random Oracle Model,” 9666:358–87. Springer, 2016. <a href=\"https://doi.org/10.1007/978-3-662-49896-5_13\">https://doi.org/10.1007/978-3-662-49896-5_13</a>.","ieee":"J. F. Alwen, B. Chen, C. Kamath Hosdurg, V. Kolmogorov, K. Z. Pietrzak, and S. Tessaro, “On the complexity of scrypt and proofs of space in the parallel random oracle model,” presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Vienna, Austria, 2016, vol. 9666, pp. 358–387.","mla":"Alwen, Joel F., et al. <i>On the Complexity of Scrypt and Proofs of Space in the Parallel Random Oracle Model</i>. Vol. 9666, Springer, 2016, pp. 358–87, doi:<a href=\"https://doi.org/10.1007/978-3-662-49896-5_13\">10.1007/978-3-662-49896-5_13</a>.","ama":"Alwen JF, Chen B, Kamath Hosdurg C, Kolmogorov V, Pietrzak KZ, Tessaro S. On the complexity of scrypt and proofs of space in the parallel random oracle model. In: Vol 9666. Springer; 2016:358-387. doi:<a href=\"https://doi.org/10.1007/978-3-662-49896-5_13\">10.1007/978-3-662-49896-5_13</a>","apa":"Alwen, J. F., Chen, B., Kamath Hosdurg, C., Kolmogorov, V., Pietrzak, K. Z., &#38; Tessaro, S. (2016). On the complexity of scrypt and proofs of space in the parallel random oracle model (Vol. 9666, pp. 358–387). Presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Vienna, Austria: Springer. <a href=\"https://doi.org/10.1007/978-3-662-49896-5_13\">https://doi.org/10.1007/978-3-662-49896-5_13</a>","ista":"Alwen JF, Chen B, Kamath Hosdurg C, Kolmogorov V, Pietrzak KZ, Tessaro S. 2016. On the complexity of scrypt and proofs of space in the parallel random oracle model. EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS, vol. 9666, 358–387."},"oa":1,"quality_controlled":"1","oa_version":"Submitted Version","page":"358 - 387","volume":9666,"alternative_title":["LNCS"],"main_file_link":[{"url":"https://eprint.iacr.org/2016/100","open_access":"1"}],"publist_id":"6103","acknowledgement":"Joël Alwen, Chethan Kamath, and Krzysztof Pietrzak’s research is partially supported by an ERC starting grant (259668-PSPC). Vladimir Kolmogorov is partially supported by an ERC consolidator grant (616160-DOICV). Binyi Chen was partially supported by NSF grants CNS-1423566 and CNS-1514526, and a gift from the Gareatis Foundation. Stefano Tessaro was partially supported by NSF grants CNS-1423566, CNS-1528178, a Hellman Fellowship, and the Glen and Susanne Culler Chair.\r\n\r\nThis work was done in part while the authors were visiting the Simons Institute for the Theory of Computing, supported by the Simons Foundation and by the DIMACS/Simons Collaboration in Cryptography through NSF grant CNS-1523467.","project":[{"_id":"258C570E-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"259668","name":"Provable Security for Physical Cryptography"},{"_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice"}],"publisher":"Springer","title":"On the complexity of scrypt and proofs of space in the parallel random oracle model","status":"public","department":[{"_id":"KrPi"},{"_id":"VlKo"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","abstract":[{"text":"We study the time-and memory-complexities of the problem of computing labels of (multiple) randomly selected challenge-nodes in a directed acyclic graph. The w-bit label of a node is the hash of the labels of its parents, and the hash function is modeled as a random oracle. Specific instances of this problem underlie both proofs of space [Dziembowski et al. CRYPTO’15] as well as popular memory-hard functions like scrypt. As our main tool, we introduce the new notion of a probabilistic parallel entangled pebbling game, a new type of combinatorial pebbling game on a graph, which is closely related to the labeling game on the same graph. As a first application of our framework, we prove that for scrypt, when the underlying hash function is invoked n times, the cumulative memory complexity (CMC) (a notion recently introduced by Alwen and Serbinenko (STOC’15) to capture amortized memory-hardness for parallel adversaries) is at least Ω(w · (n/ log(n))2). This bound holds for adversaries that can store many natural functions of the labels (e.g., linear combinations), but still not arbitrary functions thereof. We then introduce and study a combinatorial quantity, and show how a sufficiently small upper bound on it (which we conjecture) extends our CMC bound for scrypt to hold against arbitrary adversaries. We also show that such an upper bound solves the main open problem for proofs-of-space protocols: namely, establishing that the time complexity of computing the label of a random node in a graph on n nodes (given an initial kw-bit state) reduces tightly to the time complexity for black pebbling on the same graph (given an initial k-node pebbling).","lang":"eng"}],"author":[{"id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","full_name":"Alwen, Joel F","first_name":"Joel F","last_name":"Alwen"},{"last_name":"Chen","first_name":"Binyi","full_name":"Chen, Binyi"},{"id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","last_name":"Kamath Hosdurg","first_name":"Chethan","full_name":"Kamath Hosdurg, Chethan"},{"last_name":"Kolmogorov","first_name":"Vladimir","full_name":"Kolmogorov, Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Stefano","last_name":"Tessaro","full_name":"Tessaro, Stefano"}],"ec_funded":1,"date_created":"2018-12-11T11:50:51Z","conference":{"location":"Vienna, Austria","start_date":"2016-05-08","end_date":"2016-05-12","name":"EUROCRYPT: Theory and Applications of Cryptographic Techniques"},"_id":"1231","scopus_import":1,"date_published":"2016-04-28T00:00:00Z","month":"04","language":[{"iso":"eng"}],"year":"2016","doi":"10.1007/978-3-662-49896-5_13","date_updated":"2021-01-12T06:49:15Z","type":"conference","intvolume":"      9666","publication_status":"published"}]