Cryptology ePrint Archive: Report 2015/1250

Adaptively Secure Garbled Circuits from One-Way Functions

Brett Hemenway and Zahra Jafargholi and Rafail Ostrovsky and 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.

Category / Keywords:

Date: received 1 Jan 2016

Contact author: wichs at cs neu edu

Available format(s): PDF | BibTeX Citation

Version: 20160102:211917 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]