Justin Holmgren: Succinctly Garbling and Obfuscating RAM programs

Friday, May 1, 2015 - 10:30am to 12:00pm
Location: 
D-463 Star
Speaker: 
Justin Holmgren
Seminar group: 
Cryptography and Information Security (CIS) Seminar
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
Vaikuntanathan.