Tree-based Oblivious RAM and Applications
Elaine Shi - University of Maryland
Aug 27, 2014
AbstractOblivious RAM (ORAM), originally proposed by Goldreich and Ostrovsky, is a cryptographic construction for provably obfuscating access patterns to sensitive data during computation. Since the initial proposal of Oblivious RAM, the two biggest open questions in this area are 1) whether ORAM can be made practical; and 2) whether Goldreich and Ostrovsky's ORAM lower bound is tight.
In this talk, I will introduce a new tree-based paradigm for constructing Oblivious RAMs. This new paradigm has not only yielded extremely simple constructions, but also given encouraging answers to the above questions. Notably, in this the tree-based framework, we construct Path ORAM and Circuit ORAM. The former has enabled, for the first time, ORAM-capable secure processors to be prototyped; while the latter is, to date, the ORAM scheme of choice in cryptographic secure computation. Moreover, Circuit ORAM also shows that certain stronger interpretations of Goldreich and Ostrovksy's ORAM lower bound are tight.
Finally, I will describe programming language techniques for memory-trace oblivious program execution. We not only provide formal security guarantees through new type systems, but also enable compile-time optimizations that lead to order-of-magnitude speedup in practice.
About the SpeakerElaine Shi is an Assistant Professor in the Department of Computer Science at the University of Maryland. Her research combines theory, programming languages, and systems techniques to design new computing platforms that are secure by design. Elaine's work has been recognized with several awards, including an NSA Best Scientific Cybersecurity Paper Award, a UMD Invention of the Year Award, and an ACM CCS Best Student Paper Award. Elaine is the recipient of a Sloan Research Fellowship (2014), Google Faculty Research Awards (2013 and 2014), and winner of the IJCNN/Kaggle Social Network Contest (2011). Elaine obtained her Ph.D. from Carnegie Mellon University. Prior to joining Maryland, she was a research scientist at the Palo Alto Research Center (PARC) and UC Berkeley.
Unless otherwise noted, the security seminar is held on Wednesdays at 4:30P.M. STEW G52, West Lafayette Campus. More information...