Our solutions are built from non-reusable garbled RAM in conjunction with new types of reusable garbled circuits that are more efficient than prior solutions but only satisfy weaker security. For the basic setting without a persistent database, we can instantiate the required reusable garbled circuits using indistinguishability obfuscation. For the more complex setting with a persistent database we need stronger notions of obfuscation. Our basic solution also requires the client to perform a one-time preprocessing step to garble a program at the cost of its RAM run-time, and we can avoid this cost using stronger notions of obfuscation. It remains an open problem to instantiate these new types of reusable garbled circuits under weaker assumptions, possibly avoiding obfuscation altogether.
Category / Keywords: cryptographic protocols / Original Publication (with major differences): FOCS 2014 Date: received 27 Feb 2014, last revised 25 Aug 2014 Contact author: wichs at ccs neu edu Available format(s): PDF | BibTeX Citation Version: 20140825:204904 (All versions of this report) Short URL: ia.cr/2014/148