[{"isi":1,"publisher":"Springer Nature","status":"public","intvolume":"     13043","quality_controlled":"1","department":[{"_id":"KrPi"}],"page":"397-428","date_created":"2021-12-05T23:01:42Z","month":"11","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"doi":"10.1007/978-3-030-90453-1_14","language":[{"iso":"eng"}],"title":"Trojan-resilience without cryptography","conference":{"location":"Raleigh, NC, United States","name":"TCC: Theory of Cryptography Conference","end_date":"2021-11-11","start_date":"2021-11-08"},"citation":{"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>.","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.","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.","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>.","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."},"ec_funded":1,"author":[{"full_name":"Chakraborty, Suvradip","first_name":"Suvradip","last_name":"Chakraborty","id":"B9CD0494-D033-11E9-B219-A439E6697425"},{"full_name":"Dziembowski, Stefan","first_name":"Stefan","last_name":"Dziembowski"},{"first_name":"Małgorzata","full_name":"Gałązka, Małgorzata","last_name":"Gałązka"},{"first_name":"Tomasz","full_name":"Lizurej, Tomasz","last_name":"Lizurej"},{"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":"Yeo","full_name":"Yeo, Michelle X","first_name":"Michelle X","id":"2D82B818-F248-11E8-B48F-1D18A9856A87"}],"type":"conference","alternative_title":["LNCS"],"day":"04","main_file_link":[{"url":"https://eprint.iacr.org/2021/1224","open_access":"1"}],"oa":1,"publication_status":"published","volume":13043,"article_processing_charge":"No","date_published":"2021-11-04T00:00:00Z","_id":"10407","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"}],"publication_identifier":{"issn":["0302-9743"],"isbn":["9-783-0309-0452-4"],"eissn":["1611-3349"]},"external_id":{"isi":["000728364000014"]},"scopus_import":"1","date_updated":"2023-08-14T13:07:46Z","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","oa_version":"Preprint","year":"2021"},{"year":"2021","oa_version":"Preprint","publication_identifier":{"isbn":["9-783-0309-0452-4"],"issn":["0302-9743"],"eissn":["1611-3349"]},"external_id":{"isi":["000728364000017"]},"scopus_import":"1","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","date_updated":"2023-08-17T06:21:38Z","article_processing_charge":"No","_id":"10409","date_published":"2021-11-04T00:00:00Z","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"}],"oa":1,"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2021/926"}],"publication_status":"published","volume":"13043 ","title":"On treewidth, separators and Yao’s garbling","conference":{"location":"Raleigh, NC, United States","name":"TCC: Theory of Cryptography","start_date":"2021-11-08","end_date":"2021-11-11"},"citation":{"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>.","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.","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.","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>","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>","short":"C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, in:, 19th International Conference, Springer Nature, 2021, pp. 486–517."},"ec_funded":1,"author":[{"id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","full_name":"Kamath Hosdurg, Chethan","first_name":"Chethan","last_name":"Kamath Hosdurg"},{"full_name":"Klein, Karen","first_name":"Karen","last_name":"Klein","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Pietrzak","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"}],"type":"conference","alternative_title":["LNCS"],"day":"04","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"10044"}]},"project":[{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","grant_number":"682815"}],"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"}],"page":"486-517","date_created":"2021-12-05T23:01:43Z","month":"11","isi":1,"publisher":"Springer Nature","status":"public","publication":"19th International Conference","department":[{"_id":"KrPi"}],"quality_controlled":"1"},{"oa_version":"Preprint","year":"2021","date_updated":"2023-10-17T09:24:07Z","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","external_id":{"isi":["000728364000019"]},"scopus_import":"1","publication_identifier":{"issn":["0302-9743"],"isbn":["9-783-0309-0452-4"],"eissn":["1611-3349"]},"article_processing_charge":"No","date_published":"2021-11-04T00:00:00Z","_id":"10410","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."}],"publication_status":"published","main_file_link":[{"open_access":"1","url":"https://ia.cr/2021/059"}],"oa":1,"volume":13043,"ec_funded":1,"citation":{"short":"C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, M. Walter, in:, 19th International Conference, Springer Nature, 2021, pp. 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>","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>","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>.","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.","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.","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>."},"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","day":"04","alternative_title":["LNCS"],"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","last_name":"Klein","full_name":"Klein, Karen","first_name":"Karen"},{"orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z"},{"last_name":"Walter","first_name":"Michael","full_name":"Walter, Michael","orcid":"0000-0003-3186-2482","id":"488F98B0-F248-11E8-B48F-1D18A9856A87"}],"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).","related_material":{"record":[{"id":"10048","relation":"earlier_version","status":"public"}]},"project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"language":[{"iso":"eng"}],"doi":"10.1007/978-3-030-90453-1_19","page":"550-581","month":"11","date_created":"2021-12-05T23:01:43Z","publisher":"Springer Nature","isi":1,"quality_controlled":"1","department":[{"_id":"KrPi"}],"publication":"19th International Conference","intvolume":"     13043","status":"public"}]