Adaptively Secure Garbled Circuits from One-Way Functions.
Brett Hemnway, Zhara Jafargholi, Rafail Ostrovsky, Alessandra Scafuro, Daniel WichsAbstract:
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 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 20(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|