Distributed Oblivious RAM for Secure Two-Party Computation
Steve Lu, Rafail Ostrovsky,
Abstract:
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. In the heart of our construction is a new Oblivious RAM construction where a client interacts with two non –communicating servers. Our two –server Oblivious RAM for n reads⁄writs requires o(n) memory for the servers, O(1) memory for the client, and O(logn) amortized read⁄write overhead for data access. The constants in the big-O notation are tiny, and we show that storage and data access overhead of our solution concretely compares favorably to the state-of-the-art single-server schemes. Our protocol enjoys an important feature from a practical perspective as well. At the heart of almost all previous single-server Oblivious RAM solutions, a crucial but inefficient process known as oblivious sorting was required. In our two-server model, we describe a new technique to bypass oblivious sorting , and show how this can be carefully blended with existing techniques to attain a more practical Oblivious RAM protocol in comparison to all prior work.
As alluded above, our two-server Oblivious RAM protocol leads to novel application in the realm of secure two-party RAM program computation. We observe that in the secure two party computation, Alice and Bob can play the roles of two non-colluding servers. 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.
comment: TCC 2013 PP: 377-396
Fetch PDF file of the paper
| Back to Publications List |