Practical Oblivious Computation: From Theory to Hardware to Compiler
Prof. Dr. Elaine Shi
University of Maryland; USA
CISPA Distinguished Lecture Series
Elaine Shi is an Assistant Professor in the Computer Science Department at University of Maryland, College Park. She obtained her Ph.D. from Carnegie Mellon University in 2008, and was a research scientist at PARC and UC Berkeley prior to joining Maryland. Elaine's research combines theory and hands-on systems building to design and develop new systems that offer security and/or privacy by design. She has extensive expertise in cloud computing security, network security, Trusted Computing, applied cryptography, as well as privacy. Apart from security and cryptography, Elaine is also interested in data mining. She and her team won the IJCNN Social Network Challenge in 2011.
I will describe a new binary-tree based paradigm of constructing Oblivious RAM, leading to extremely simple constructions. Within this framework, I will describe Path ORAM. Under reasonable assumptions about the block size, Path ORAM achieves O(log n) bandwidth overhead with just a little more than O(log n) trusted cache --- this is nearly optimal in light of Goldreich and Ostrovsky's lower bound. Based on Path ORAM, we implement the first real-life ORAM-capable secure processor prototype called Phantom. We run real-world programs such as sqlite on top of Phantom, and demonstrate reasonable practical performance. Then, I will describe programming language techniques that can compile a program into its memory-trace oblivious equivalent, while achieving order-of-magnitude speedup in comparison with the naive approach of placing all variables in a single, large ORAM. Finally, I will describe a vision of building a cloud computing platform secure against physical attacks.