Garbling and Outsourcing RAM Computation

Speaker: Daniel Wichs , Northeastern University

Date: Friday, March 21, 2014

Time: 10:30 AM to 12:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-449

Event Type:

Room Description:

Host: Vinod Vaikuntanathan, TOC, CSAIL, MIT

Contact: Holly A Jones, hjones01@csail.mit.edu

Relevant URL: http://toc.csail.mit.edu/node/540

Speaker URL: None

Speaker Photo:
None

Reminders to: cis-seminars@csail.mit.edu, seminars@csail.mit.edu

Reminder Subject: TALK: Garbling and Outsourcing RAM Computation

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:

http://eprint.iacr.org/2014/148
http://eprint.iacr.org/2014/082
http://eprint.iacr.org/2014/083

which are joint with Craig Gentry, Shai Halevi, Steve Lu, Rafail Ostrovsky and Mariana Raykova

Research Areas:

Impact Areas:

See other events that are part of the Cryptography and Information Security Seminar Seminars Fall 2013 / Spring 2014.

Created by Holly A Jones at Monday, March 17, 2014 at 9:26 AM.