Paper 2015/1250

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 $$ and an input $$ in a way that reveals the output $$ 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 $$ prior to seeing the garbled circuit. It has remained an open problem to achieve adaptive security, where the adversary can choose $$ 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 $$ of the circuit, which corresponds to the space complexity of the computation, but is independent of the circuit's depth $$. Alternately, we can also get an instantiation where the on-line complexity is only proportional to the input/output size and the depth $$ of the circuit but independent of its width $$, albeit in this case we incur a $$ 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.