---
res:
  bibo_abstract:
  - 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.@eng
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Chethan
      foaf_name: Kamath Hosdurg, Chethan
      foaf_surname: Kamath Hosdurg
      foaf_workInfoHomepage: http://www.librecat.org/personId=4BD3F30E-F248-11E8-B48F-1D18A9856A87
    orcid: 0009-0006-6812-7317
  - foaf_Person:
      foaf_givenName: Karen
      foaf_name: Klein, Karen
      foaf_surname: Klein
      foaf_workInfoHomepage: http://www.librecat.org/personId=3E83A2F8-F248-11E8-B48F-1D18A9856A87
  - foaf_Person:
      foaf_givenName: Krzysztof Z
      foaf_name: Pietrzak, Krzysztof Z
      foaf_surname: Pietrzak
      foaf_workInfoHomepage: http://www.librecat.org/personId=3E04A7AA-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0002-9139-1654
  bibo_doi: 10.1007/978-3-030-90453-1_17
  bibo_volume: '13043 '
  dct_date: 2021^xs_gYear
  dct_identifier:
  - UT:000728364000017
  dct_isPartOf:
  - http://id.crossref.org/issn/0302-9743
  - http://id.crossref.org/issn/1611-3349
  - http://id.crossref.org/issn/9-783-0309-0452-4
  dct_language: eng
  dct_publisher: Springer Nature@
  dct_title: On treewidth, separators and Yao’s garbling@
...