Tree-based Oblivious RAM and Applications

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.