-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.Category / Keywords: Oblivious RAM, Cloud Computing, Multi-Server Model, Software Protection, Secure Computation. Date: received 14 Jul 2011, last revised 5 Nov 2011 Contact author: steve at stealthsoftwareinc com Available format(s): PDF | BibTeX Citation Version: 20111106:033319 (All versions of this report) Short URL: ia.cr/2011/384 Discussion forum: Show discussion | Start new discussion