Elaine (Runting) Shi
January 30, 2015 at 12:00 PM in 380 Soda Hall
Oblivious computation refers to the ability to compute on "encrypted" data, such that neither intermediate results nor the program's runtime behavior reveal anything about secret inputs. Oblivious computation carries great promise in various domains such as financial and genomic computation, and can enable businesses and individuals to monetize their data without compromising their privacy. Numerous challenges lie in the way of making oblivious computation practical and accessible to real-life developers. In this talk, I will describe our efforts that combine novel algorithms and programming language techniques towards achieving this goal. I will first present a novel, binary-tree based paradigm for constructing Oblivious RAM (ORAM) schemes. ORAM is a generic and powerful primitive that is central to realizing oblivious computation using either trusted hardware or cryptographic secure computation. Our binary-tree based ORAM constructions not only made it possible to implement ORAM atop secure processors and secure multi-party computation for the first time, but also address a twenty-seven year open theoretical problem -- by showing that the well-known Goldreich-Ostrovsky ORAM lower bound is tight under certain parameter ranges. I will also describe programming language techniques for accelerating oblivious computation and for making oblivious computation accessible to real-life programmers who are not security experts. Finally, I will describe exciting future research directions, including our vision of developing a unified programming framework for modern cryptography.