Alessandra Scafuro: New Realizations of Adaptively Secure Garbled Circuits

Friday, November 6, 2015 - 10:30am to 12:00pm
Hewlett G882
Alessandra Scafuro, BU and Northeastern
Abstract:   A garbled circuit can be evaluated on a single garbled input without revealing any information beyond the output.  The size of the garbled input and the time that it takes to create it should be much smaller than the size of the circuit, and ideally only proportional to the input size.  Yao’s garbled circuit construction achieves this with static security when the input is chosen by the adversary prior to seeing the garbled circuit. It had remained a long-standing open problem to achieve adaptive security where the adversary can choose the input adaptively after seeing the garbled circuit.
In this work we provide a framework that allows us to lightly modify Yao’s garbling scheme and prove adaptive security under various parameter regimes. In particular, we can get a scheme based on one-way functions where the size of the garbled input is only proportional to the width of the circuit (which corresponds to the space complexity of the computation) rather that the entire size of the circuit. More broadly, we develop a connection between constructing adaptively secure schemes in our framework and a certain type of pebble complexity.
Joint work with Brett Hemenway, Zahra Jafargholi, Rafail Ostrovsky, Daniel Wichs.