Justin Holmgren: Succinctly Garbling and Obfuscating RAM programs
Date: Friday, May 01, 2015
Time: 10:30 AM to 12:00 PM Note: all times are in the Eastern Time Zone
Location: D-463 Star
Host: Vinod Vaikuntanathan
Contact: Deborah Lehto, 617.324.7303, email@example.com
Speaker URL: None
TALK: Justin Holmgren: Succinctly Garbling and Obfuscating RAM programs
Abstract: Program obfuscation, and in particular the notion of Indistinguishability Obfuscation (IO) has been shown to
have wide-spread applications in cryptography and beyond. However, current candidate indistinguishability obfuscators
generate programs whose size and runtime are proportional to the circuit representation of the input program --- even for input programs
that are written for RAM machines. This does not allow obfuscated programs to use the capabilities of modern computers.
In this talk, we show how to construct succinct and efficient IO for RAM programs given IO
for circuits. Our techniques involve developing a special "pseudo-information
theoretic" encryption system, and identifying an Oblivious RAM transformation
(ORAM) which is forward secure and whose security follows from simple
invariants. As an intermediate result of independent interest, we obtain a
garbling scheme for RAM programs with better parameters and under weaker
assumptions. A garbling scheme is a method of encoding a RAM program
together with a single input, so that one can evaluate the program, but learn
nothing more than the output value.
This talk is based on joint work with Ran Canetti, Abhishek Jain, and Vinod
Created by Deborah Goodwin at Tuesday, March 24, 2015 at 2:32 PM.