Practical Oblivious Computation: From Theory to Hardware to Compiler
Elaine Shi
Abstract:
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.