---
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 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.@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
  dct_date: 2021^xs_gYear
  dct_language: eng
  dct_publisher: International Association for Cryptologic Research@
  dct_title: On treewidth, separators and Yao's garbling@
...