Paper 2021/926

On Treewidth, Separators and Yao's Garbling

Chethan Kamath, Karen Klein, and Krzysztof Pietrzak


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.

Available format(s)
Publication info
Preprint. MINOR revision.
adaptive securitygarbled circuits
Contact author(s)
ckamath @ protonmail com
kklein @ ist ac at
pietrzak @ ist ac at
2021-07-09: received
Short URL
Creative Commons Attribution


      author = {Chethan Kamath and Karen Klein and Krzysztof Pietrzak},
      title = {On Treewidth, Separators and Yao's Garbling},
      howpublished = {Cryptology ePrint Archive, Paper 2021/926},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.