---
_id: '10044'
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.
acknowledgement: 'We would like to thank Daniel Wichs for helpful discussions on the
  landscape of adaptive security of Yao’s garbling.  '
article_number: 2021/926
article_processing_charge: No
author:
- first_name: Chethan
  full_name: Kamath Hosdurg, Chethan
  id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
  last_name: Kamath Hosdurg
  orcid: 0009-0006-6812-7317
- 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: <i>19th Theory of Cryptography Conference 2021</i>. International
    Association for Cryptologic Research; 2021.'
  apa: 'Kamath Hosdurg, C., Klein, K., &#38; Pietrzak, K. Z. (2021). On treewidth,
    separators and Yao’s garbling. In <i>19th Theory of Cryptography Conference 2021</i>.
    Raleigh, NC, United States: International Association for Cryptologic Research.'
  chicago: Kamath Hosdurg, Chethan, Karen Klein, and Krzysztof Z Pietrzak. “On Treewidth,
    Separators and Yao’s Garbling.” In <i>19th Theory of Cryptography Conference 2021</i>.
    International Association for Cryptologic Research, 2021.
  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.
  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.
  short: C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, in:, 19th Theory of Cryptography
    Conference 2021, International Association for Cryptologic Research, 2021.
conference:
  end_date: 2021-11-11
  location: Raleigh, NC, United States
  name: 'TCC: Theory of Cryptography Conference'
  start_date: 2021-11-08
cryptoeprintid: 1
das_tickbox: '1'
date_created: 2021-09-24T12:01:34Z
date_published: 2021-07-08T00:00:00Z
date_updated: 2026-07-06T13:15:57Z
day: '08'
department:
- _id: KrPi
ec_funded: 1
external_id:
  cryptoeprintid:
  - 2021/926
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprint.iacr.org/2021/926
month: '07'
oa: 1
oa_version: Preprint
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '682815'
  name: Teaching Old Crypto New Tricks
publication: 19th Theory of Cryptography Conference 2021
publication_status: published
publisher: International Association for Cryptologic Research
quality_controlled: '1'
related_material:
  record:
  - id: '10409'
    relation: later_version
    status: public
  - id: '10035'
    relation: dissertation_contains
    status: public
status: public
title: On treewidth, separators and Yao's garbling
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2021'
...