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.