Paper 2021/926

On Treewidth, Separators and Yao's Garbling

Chethan Kamath, Karen Klein, and Krzysztof Pietrzak

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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. Minor revision.
Keywords
adaptive securitygarbled circuits
Contact author(s)
ckamath @ protonmail com
kklein @ ist ac at
pietrzak @ ist ac at
History
2021-07-09: received
Short URL
https://ia.cr/2021/926
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/926,
      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{https://eprint.iacr.org/2021/926}},
      url = {https://eprint.iacr.org/2021/926}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.