Abstract: 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 applications, and can enable businesses and individuals to monetize their data without compromising their privacy.
Two essential challenges lie in the way of making oblivious computation practical: 1) the efficiency of foundational cryptographic building blocks; and 2) ease-of-adoption by non-specialist programmers. In this talk, I will describe our efforts that combine algorithms, programming languages, and systems building to overcome these challenges.
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 based on either trusted hardware or cryptographic secure computation. Our new ORAM constructions not only solve a twenty-seven year open theoretical challenge, but also allow ORAM to evolve from a theoretical primitive to a practical building block. Specifically, we made it possible, for the first time, to implement ORAM atop secure processors as well as secure multi-party computation.
Next, I will present programming language techniques that not only accelerate oblivious computation, but also make it accessible to real-life programmers who are not security experts. Based on these algorithmic and programming language advances, we have built new platforms for oblivious computation and developed various demo applications such as common data structures, data mining, graph algorithms, and streaming algorithms. Evaluation results suggest that over a duration of three years, our work has led to four to five orders of magnitude performance improvement for moderately large data sizes, and has enabled a dramatic reduction in application development effort. Part of our framework is in the process of being publicly released via http://www.oblivm.com.
Elaine Shi is an Assistant Professor in the Department of Computer Science at the University of Maryland. Her research combines theory, programming languages, and systems techniques to design computing platforms that are efficient, easy to program, and provably secure. Elaine's research has been recognized with several awards, including an NSA Best Scientific Cybersecurity Paper Award, a UMD Invention of the Year Award, and an ACM CCS Best Student Paper Award. Elaine is the recipient of a Sloan Research Fellowship (2014), Google Faculty Research Awards (2013 and 2014), and winner of the IJCNN/Kaggle Social Network Challenge (2011). Elaine obtained her Ph.D. from Carnegie Mellon University. Prior to joining Maryland, she was a research scientist at the Palo Alto Research Center (PARC) and UC Berkeley.