CERIAS - Center for Education and Research in Information Assurance and Security

Skip Navigation
Purdue University - Discovery Park
Center for Education and Research in Information Assurance and Security

Tree-based Oblivious RAM and Applications

Elaine Shi

Elaine Shi - University of Maryland

Aug 27, 2014


Oblivious 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 Speaker

Elaine 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 (Suite 050B), West Lafayette Campus. More information...


The views, opinions and assumptions expressed in these videos are those of the presenter and do not necessarily reflect the official policy or position of CERIAS or Purdue University. All content included in these videos, are the property of Purdue University, the presenter and/or the presenter’s organization, and protected by U.S. and international copyright laws. The collection, arrangement and assembly of all content in these videos and on the hosting website exclusive property of Purdue University. You may not copy, reproduce, distribute, publish, display, perform, modify, create derivative works, transmit, or in any other way exploit any part of copyrighted material without permission from CERIAS, Purdue University.