PhD Proposal: Efficient Oblivious Computation

Kartik Nayak
04.21.2017 09:00 to 10:30
AVW 3450

A lot of potentially sensitive user data is increasingly being stored on untrusted cloud servers. The cloud service providers may compute onthis data either on user’s behalf, i.e., by acting as a computation resource provider or to collect some statistics on multiple users’ data for its own business needs. Commercially available trusted hardware solutions such as Intel SGX provide confidentiality and integrity but leak side channels such as memory access patterns. Also, while secure multiparty computation can help perform computation without revealing user data, an essential ingredient in these protocols is to represent the RAM program as a circuit. A potential solution is to use an Oblivious RAM, which is a cryptographic primitive that makes any RAM program memory-oblivious, i.e., it hides access patterns to data. Such an oblivious program can also be easily converted into circuits which are required for secure computation.

While Oblivious RAMs can support arbitrary access patterns, they incur a high bandwidth blowup. In this paper, I will present GraphSC, a framework to efficiently implement a class of algorithms called graph-parallel algorithms on secure computation. In addition to generating efficient oblivious graph- parallel operations, GraphSC brings parallelism to the secure implementation and provides a programming paradigm that allows non-cryptography experts to write secure code.

Finally, I will discuss my proposed work. Specifically, I will discuss

(1) designing oblivious algorithms for privacy preserving neural networks (2) designing an efficient perfectly secure ORAM construction, i.e., an ORAM construction with no failure and (3) writing a systemization of knowledge paper on Oblivious RAMs.

Co-chairs: Dr. Jonathan Katz and Dr. Elaine Shi
Dept rep: Dr. Hal Daume III
Member: Dr. Mike Hicks