- Garbling and Outsourcing RA...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in March 2014
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:
Created by Holly A Jones at Monday, March 17, 2014 at 9:26 AM.