Oblivious RAM: From Theory to Large-scale Real-world Deployment

A Google TechTalk, presented Elaine Shi, by 2023-11-08
ABSTRACT: In this talk, I will give a brief tutorial of Oblivious RAM (ORAM). I will talk about how ORAM evolved from a theoretical concept to large-scale real-world deployment, and the various emerging demands and use cases of ORAM in both the blockchain community and for traditional cloud service providers. In particular, I will talk about Signal's deployment of Path ORAM over their billion-sized database, and how ORAM allowed them to cut their 500 servers downto 6 servers.
Finally, I will describe a new initiative to build an open-source Oblivious STL library, aiming to provide an oblivious counterpart of the standard STL library.
I will describe our initial efforts at building Oblivious STL. Specifically, I will focus on how using external-memory algorithms techniques can allow us to achieve a 10-100x performance improvement over state-of-the-art implementations for hardware enclaves. In particular, while the literature on ORAM typically uses computational overhead as the performance metric, for hardware enclaves, the number of page swaps is often the dominant metric. Through the help of external-memory algorithms, we can achieve an asymptotical improvement in the number of page swaps.
The speaker is Elaine Shi (Carnegie Mellon University)