---
_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'
...