Paper 2010/366

Oblivious RAM Revisited

Benny Pinkas and Tzachy Reinman


We reinvestigate the oblivious RAM concept introduced by Goldreich and Ostrovsky, which enables a client, that can store locally only a constant amount of data, to store remotely $n$ data items, and access them while hiding the identities of the items which are being accessed. Oblivious RAM is often cited as a powerful tool, which can be used, for example, for search on encrypted data or for preventing cache attacks. However, oblivious RAM it is also commonly considered to be impractical due to its overhead, which is asymptotically efficient but is quite high: each data request is replaced by $O(\log^4 n)$ requests, or by $O(\log^3 n)$ requests where the constant in the ``$O$'' notation is a few thousands. In addition, $O(n \log n)$ external memory is required in order to store the $n$ data items. We redesign the oblivious RAM protocol using modern tools, namely Cuckoo hashing and a new oblivious sorting algorithm. The resulting protocol uses only $O(n)$ external memory, and replaces each data request by only $O(\log^2 n)$ requests (with a small constant). This analysis is validated by experiments that we ran.

Available format(s)
Publication info
Published elsewhere. This is a full version. A proceedings version is published in Crypto 2010.
Secure two-party computationoblivious RAM
Contact author(s)
reinman @ cs huji ac il
2010-06-25: received
Short URL
Creative Commons Attribution


      author = {Benny Pinkas and Tzachy Reinman},
      title = {Oblivious RAM Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2010/366},
      year = {2010},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.