--- _id: '10409' 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. 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. alternative_title: - LNCS article_processing_charge: No author: - first_name: Chethan full_name: Kamath Hosdurg, Chethan id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87 last_name: Kamath Hosdurg - first_name: Karen full_name: Klein, Karen id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87 last_name: Klein - first_name: Krzysztof Z full_name: Pietrzak, Krzysztof Z id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87 last_name: Pietrzak orcid: 0000-0002-9139-1654 citation: ama: 'Kamath Hosdurg C, Klein K, Pietrzak KZ. On treewidth, separators and Yao’s garbling. In: 19th International Conference. Vol 13043. Springer Nature; 2021:486-517. doi:10.1007/978-3-030-90453-1_17' apa: 'Kamath Hosdurg, C., Klein, K., & Pietrzak, K. Z. (2021). On treewidth, separators and Yao’s garbling. In 19th International Conference (Vol. 13043, pp. 486–517). Raleigh, NC, United States: Springer Nature. https://doi.org/10.1007/978-3-030-90453-1_17' chicago: Kamath Hosdurg, Chethan, Karen Klein, and Krzysztof Z Pietrzak. “On Treewidth, Separators and Yao’s Garbling.” In 19th International Conference, 13043:486–517. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-90453-1_17. ieee: C. Kamath Hosdurg, K. Klein, and K. Z. Pietrzak, “On treewidth, separators and Yao’s garbling,” in 19th International Conference, 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.' mla: Kamath Hosdurg, Chethan, et al. “On Treewidth, Separators and Yao’s Garbling.” 19th International Conference, vol. 13043, Springer Nature, 2021, pp. 486–517, doi:10.1007/978-3-030-90453-1_17. short: C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, in:, 19th International Conference, Springer Nature, 2021, pp. 486–517. conference: end_date: 2021-11-11 location: Raleigh, NC, United States name: 'TCC: Theory of Cryptography' start_date: 2021-11-08 date_created: 2021-12-05T23:01:43Z date_published: 2021-11-04T00:00:00Z date_updated: 2023-08-17T06:21:38Z day: '04' department: - _id: KrPi doi: 10.1007/978-3-030-90453-1_17 ec_funded: 1 external_id: isi: - '000728364000017' isi: 1 language: - iso: eng main_file_link: - open_access: '1' url: https://eprint.iacr.org/2021/926 month: '11' oa: 1 oa_version: Preprint page: 486-517 project: - _id: 258AA5B2-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '682815' name: Teaching Old Crypto New Tricks publication: 19th International Conference publication_identifier: eissn: - 1611-3349 isbn: - 9-783-0309-0452-4 issn: - 0302-9743 publication_status: published publisher: Springer Nature quality_controlled: '1' related_material: record: - id: '10044' relation: earlier_version status: public scopus_import: '1' status: public title: On treewidth, separators and Yao’s garbling type: conference user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8 volume: '13043 ' year: '2021' ...