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
-
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},
url = {https://eprint.iacr.org/2021/926}
}
