International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: On Treewidth, Separators and Yao’s Garbling

Chethan Kamath
Karen Klein
Krzysztof Pietrzak
DOI: 10.1007/978-3-030-90453-1_17
Search ePrint
Search Google
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(\delta w log(S)), \delta being the fan-out of the circuit. The design of the strategy relies on separators, a graph-theoretic notion with connections to circuit complexity.
Video from TCC 2021
  title={On Treewidth, Separators and Yao’s Garbling},
  booktitle={Theory of Cryptography;19th International Conference},
  author={Chethan Kamath and Karen Klein and Krzysztof Pietrzak},