Our main results are as follows:
-We analyze several schemes from the literature, observing a repeated design flaw that leaks information on the memory access pattern. For some of these schemes, the leakage is actually non-negligible, while for others it is negligible.
-On the positive side, we present a new secure oblivious RAM scheme, extending a recent scheme by Goodrich and Mitzenmacher. Our scheme uses only $O(1)$ local memory, and its (amortized) overhead is $O(\log^2 n/\log\log n)$, outperforming the previously-best $O(\log^2n)$ overhead (among schemes where the client only uses $O(1)$ additional local memory).
-We also present a transformation of our scheme above (whose amortized overhead is $O(\log^2 n/\log\log n)$) into a scheme with worst-case overhead of $O(\log^2 n/\log\log n)$.
Category / Keywords: Oblivious RAM, Cuckoo Hashing, Secure Computation. Publication Info: To Appear in SODA 2012 Date: received 16 Jun 2011, last revised 4 Nov 2011 Contact author: steve at stealthsoftwareinc com Available format(s): PDF | BibTeX Citation Version: 20111104:080114 (All versions of this report) Short URL: ia.cr/2011/327 Discussion forum: Show discussion | Start new discussion