Paper 2011/384

Distributed Oblivious RAM for Secure Two-Party Computation

Steve Lu and Rafail Ostrovsky

Abstract

Secure two-party computation protocol allows two players, Alice with secret input $x$ and Bob with secret input $y$, to jointly execute an arbitrary program $\pi(x,y)$ such that only the output of the program is revealed to one or both players. In the two player setting, under computational assumptions most approaches require to first ``unroll'' $\pi$ into a circuit, and then execute this circuit in a private manner. Without unrolling the circuit, an alternative method was proposed by Ostrovsky and Shoup (in STOC 1997) with both players simulating the CPU of an oblivious RAM machine using ``off-the-shelf'' secure two-party computation to perform CPU simulation with atomic instructions implemented by circuits and relying on one of the players to implement encrypted memory. The simulation of the CPU must be done through circuit-based secure two-party computation, thus CPU ``memory'' in the Oblivious RAM simulation must be minimized, as otherwise it impacts simulation of each step of the computation. Luckily, there are multiple Oblivious RAM solutions that require $O(1)$ CPU memory in the security parameter. The Ostrovsky-Shoup compiler suffers from two drawbacks: -The best running time of Oblivious RAM simulation with $O(1)$ memory is still prohibitive and requires $O(\log^2t/\log\log t)$ overhead for running programs of length $t$ by Kushilevitz, Lu, and Ostrovsky (in SODA 2012). -The most problematic part of this approach is that all Oblivious RAM simulations, starting with Goldreich and Ostrovsky (in JACM 1996) require ``Oblivious Sorting'' that introduce a huge constant into Oblivious RAM simulation that essentially kills all practicality. In this paper, we observe that in the secure two-party computation, Alice and Bob can simulate two non-communicating databases. We show how to extend the Ostrovsky-Shoup compiler so that two non-communicating servers can eliminate all the drawbacks stated above. More specifically, we design a new Oblivious RAM protocol where a client interacts with two non-communicating servers, that supports $n$ reads and writes, and requires $O(n)$ memory for the servers, $O(1)$ memory for the client, and $O(\log n)$ amortized read/write overhead for data access. The constants in the big-O notation are tiny, and we show that the storage and data access overhead of our solution concretely compares favorably to the state-of-the-art single-server schemes. As alluded to above, 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 novel 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. This new protocol leads to a novel application in the realm of secure two-party RAM program computation. We show that our multi-server Oblivious RAM construction can be composed with an extended version of the Ostrovsky-Shoup compiler to obtain a new method for secure two-party RAM computation with lower overhead than (implicitly) existing constructions by a factor of $O(\log n/\log\log n)$ of Gordon et al.