Distributed Oblivious RAM for Secure Two-Party Computation

We present a new method for secure two-party Random Access Memory (RAM) program computation that does not require taking a program and first turning it into a circuit. The method achieves logarithmic overhead compared to an insecure program execution.

At the heart of our construction is a new Oblivious RAM protocol where a client interacts with two non-communicating servers. Our two-server Oblivious RAM for n reads/writes requires O(n) memory for the servers, O(1) memory for the client, and O(log n) amortized read/write overhead for data access. In our two-server model, we describe a new technique to bypass oblivious sorting which results in tiny constants and leads to a more practical Oblivious RAM protocol that compares favorably to the state-of-the-art single-server schemes.

Our two-server Oblivious RAM protocol leads to a novel application in the realm of secure two-party RAM program computation. We show that our Oblivious RAM construction can be composed with an extended version of the Ostrovsky-Shoup compiler to obtain a new method for secure two-party program computation with lower overhead than all existing constructions.

Joint work with Rafail Ostrovsky.