Date: Friday, February 15, 2013
Location: 3941 BBB/CSE (10:30 AM to 11:30 AM)
Title: Distributed Oblivious RAM for Secure Two-Party Computation
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.
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.
Speaker: Steve Lu
Institution:
Event Organizer: martinjs
|
