### Adaptively Secure Garbled Circuits from One-Way Functions

Brett Hemenway, Zahra Jafargholi, Rafail Ostrovsky, Alessandra Scafuro, and Daniel Wichs

##### Abstract

A garbling scheme is used to garble a circuit $C$ and an input $x$ in a way that reveals the output $C(x)$ but hides everything else. In many settings, the circuit can be garbled off-line without strict efficiency constraints, but the input must be garbled very efficiently on-line, with much lower complexity than evaluating the circuit. Yao's scheme has essentially optimal on-line complexity, but only achieves selective security, where the adversary must choose the input $x$ prior to seeing the garbled circuit. It has remained an open problem to achieve adaptive security, where the adversary can choose $x$ after seeing the garbled circuit, while preserving on-line efficiency. In this work, we modify Yao's scheme in a way that allows us to prove adaptive security under one-way functions. As our main instantiation, we get a scheme where the on-line complexity is only proportional to the width $w$ of the circuit, which corresponds to the space complexity of the computation, but is independent of the circuit's depth $d$. Alternately, we can also get an instantiation where the on-line complexity is only proportional to the input/output size and the depth $d$ of the circuit but independent of its width $w$, albeit in this case we incur a $2^{O(d)}$ security loss in our reduction. More broadly, we relate the on-line complexity of adaptively secure garbling schemes in our framework to a certain type of pebble complexity of the circuit. As our main tool, of independent interest, we develop a new notion of somewhere equivocal encryption, which allows us to efficiently equivocate on a small subset of the message bits.

Available format(s)
Publication info
Preprint. MINOR revision.
Contact author(s)
wichs @ cs neu edu
History
Short URL
https://ia.cr/2015/1250

CC BY

BibTeX

@misc{cryptoeprint:2015/1250,
author = {Brett Hemenway and Zahra Jafargholi and Rafail Ostrovsky and Alessandra Scafuro and Daniel Wichs},
title = {Adaptively Secure Garbled Circuits from One-Way Functions},
howpublished = {Cryptology ePrint Archive, Paper 2015/1250},
year = {2015},
note = {\url{https://eprint.iacr.org/2015/1250}},
url = {https://eprint.iacr.org/2015/1250}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.