Tree-based Oblivious RAM and Applications

Page Content

Page Content

Elaine Shi

Elaine Shi - University of Maryland

Aug 27, 2014

Abstract

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, West Lafayette Campus. More information...

© 1999-2014 Purdue University. All rights reserved.

Use/Reuse Guidelines

CERIAS Seminar materials are intended for educational, non-commercial use only and any or all commercial use is prohibited. Any use must attribute "The CERIAS Seminar at Purdue University." Opinions expressed in the recordings are not necessarily representative of the views of CERIAS or of Purdue University.