**
Adaptively Secure Garbled Circuits from One-Way Functions.
**

*
Brett Hemnway,
Zhara Jafargholi,
Rafail Ostrovsky,
Alessandra Scafuro,
Daniel Wichs
*

A grabling 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 inout must be garbled very efficiently *on-line*,
with much lower complexity than evaluation the circuit. Yao's garbling scheme [31]has essentially optimal on-line complexity, but only achieves *selective 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. In our main instantiation we achieve on-line complexity only proportional to width w of the circuit. Alternatively we can also get an instantiation with on-line
complexity only proportional to the depth d (and the output size) of the circuit,albiet incurring in a 2^{0(d)} security loss in our reduction. More broadly, we relate the on-line complexity of adaptively secure garbling schemes in our framework to certain type of * pebbllle*, 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.

**comment:**
CRYPTO (3) 2016: 149-178

Fetch PDF file of the paper

Back to Publications List |