On treewidth, separators and Yao's garbling

Kamath Hosdurg C, Klein K, Pietrzak KZ. On treewidth, separators and Yao’s garbling. 19th Theory of Cryptography Conference 2021. TCC: Theory of Cryptography Conference, 2021/926.

Conference Paper | Accepted | English
Department
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.
Publishing Year
Date Published
2021-07-08
Proceedings Title
19th Theory of Cryptography Conference 2021
Acknowledgement
We would like to thank Daniel Wichs for helpful discussions on the landscape of adaptive security of Yao’s garbling.
Article Number
2021/926
Conference
TCC: Theory of Cryptography Conference
Conference Location
Raleigh, NC, United States
Conference Date
2021-11-08 – 2021-11-11
IST-REx-ID

Cite this

Kamath Hosdurg C, Klein K, Pietrzak KZ. On treewidth, separators and Yao’s garbling. In: 19th Theory of Cryptography Conference 2021. International Association for Cryptologic Research.
Kamath Hosdurg, C., Klein, K., & Pietrzak, K. Z. (n.d.). On treewidth, separators and Yao’s garbling. In 19th Theory of Cryptography Conference 2021. Raleigh, NC, United States: International Association for Cryptologic Research.
Kamath Hosdurg, Chethan, Karen Klein, and Krzysztof Z Pietrzak. “On Treewidth, Separators and Yao’s Garbling.” In 19th Theory of Cryptography Conference 2021. International Association for Cryptologic Research, n.d.
C. Kamath Hosdurg, K. Klein, and K. Z. Pietrzak, “On treewidth, separators and Yao’s garbling,” in 19th Theory of Cryptography Conference 2021, Raleigh, NC, United States.
Kamath Hosdurg C, Klein K, Pietrzak KZ. On treewidth, separators and Yao’s garbling. 19th Theory of Cryptography Conference 2021. TCC: Theory of Cryptography Conference, 2021/926.
Kamath Hosdurg, Chethan, et al. “On Treewidth, Separators and Yao’s Garbling.” 19th Theory of Cryptography Conference 2021, 2021/926, International Association for Cryptologic Research.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar