Garbling and Outsourcing RAM Computation

Friday, March 21, 2014 - 10:30am to 12:00pm
32-G449 (Patil/Kiva)
Daniel Wichs, Northeastern University

Abstract:  We construct the first schemes that allow a client to privately outsource arbitrary program executions to a remote server while ensuring that: (I) the client's work is small and essentially independent of the complexity of the computation being outsourced, and (II) the server's work is only proportional to the run-time of the computation on a random access machine (RAM), rather than its potentially much larger circuit size. Furthermore, our solutions are non-interactive and have the structure of "reusable garbled RAM programs", where the client creates a garbled program which it gives to the server and later can outsource arbitrary executions of this program by providing fresh garbled inputs. 

One of the main tools in our construction is  the  simpler primitive of "non-reusable garbled RAM", defined by Lu and Ostrovsky (Eurocrypt 2013). The talk will begin by describing this simpler primitive,  the subtle difficulties that come up when proving its security, and recent provably secure instantiations. 

Our solution for "reusable garbled RAM" is built from "non-reusable garbled RAM" in conjunction with new types of "reusable garbled circuits" that are more efficient than prior solutions but have necessarily  weaker security requirements. We instantiate the required reusable garbled circuits using indistinguishability obfuscation, and it remains an open problem to find instantiations under weaker assumptions.
We also construct an an augmented notion of "reusable garbled RAM"   where the client can initially outsource a large private and persistent database to the server, and later outsource arbitrary program executions with read/write access to this database. This requires a stronger variant of  "reusable garbled circuits" and  we show how to instantiate this variant under stronger notions of obfuscation, related to "differing inputs obfuscation". Under these stronger assumptions, we can also reduce the size of the garbled RAM program and the time it takes to create it to only be proportionate to the program's description length and independent of its running time. 
The talk is based on the following works:
which are joint with  Craig Gentry, Shai Halevi, Steve Lu, Rafail Ostrovsky and Mariana Raykova