Secure computation protocols enable multiple distrusting parties, each with their own private input, to interact and perform some agreed upon computation, revealing nothing in the process beyond the result of that computation. Traditionally, protocols for secure computation are designed in the circuit model. One benefit of this approach is that circuits are stateless, which precludes the participants from learning something about the other user inputs through memory access patterns. Unfortunately, the reliance on a circuit representation is also limiting, as access to memory can provide algorithms that are asymptotically faster than circuit-based computation. Oblivious RAM protocols allow us to fix this problem, by providing a method for accessing memory obliviously -- that is, without revealing which location in memory has been fetched.  

The use of ORAM in secure computation was relatively unexplored prior to our work in this project. The fact that it can be used generically had been observed twenty years ago, but since that time, researchers in the field have begun to optimize constructions of secure computation with an eye on concrete performance. The concrete performance of a generic approach to using Oblivious RAM inside a secure computation is prohibitively expensive.  

In this project, we have explored several directions for improving the use of oblivious memory access in secure computation:  

Constructing new ORAM protocols.  ORAM was originally designed for a client/server model in which the client has storage constraints, but is allowed to see all data. In secure computation, all parties have similar storage constraints, but none may see the data. We designed new ORAM protocols for this setting, improving efficiency by leveraging the fact that the parties have linear storage. Additionally, our protocols are faster to instantiate than existing constructions in the client/server model. In this same direction, we have designed new oblivious data structures that have better memory locality, allowing the server to reduce the total number of physical memory accesses while preserving privacy. 

Constructing new languages. We developed a new programming language, called L_obliv, for writing oblivious algorithms and data structures (including ORAM). We have proven that type-correct programs in L-obliv offer probabilistic obliviousness: no matter the values of secrets, the distribution of publicly observable traces is unaffected.  

Exploring other notions of data obliviousness. We have begun the investigation of alternatives to fully oblivious computation. Specifically, we have investigated a security definition that allows some leakage in the form of memory access patterns, but admits a proof that the leakage preserves differential privacy for the users that have contributed data.

Leveraging data oblivious computation in program analysis.  We have explored methods for securely performing static analysis without revealing the details of the program. This allows us to formally verify properties of the given code while maintaining privacy. 

Last Modified: 02/14/2021
Modified by: Ruzica Piskac