Paper 2011/327

On the (In)security of Hash-based Oblivious RAM and a New Balancing Scheme

Eyal Kushilevitz, Steve Lu, and Rafail Ostrovsky

Abstract

With the gaining popularity of remote storage (e.g. in the Cloud), we consider the setting where a small, protected local machine wishes to access data on a large, untrusted remote machine. This setting was introduced in the RAM model in the context of software protection by Goldreich and Ostrovsky. A secure Oblivious RAM simulation allows for a client, with small (e.g., constant size) protected memory, to hide not only the data but also the sequence of locations it accesses (both reads and writes) in the unprotected memory of size $n$. 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)$.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. To Appear in SODA 2012
Keywords
Oblivious RAMCuckoo HashingSecure Computation.
Contact author(s)
steve @ stealthsoftwareinc com
History
2011-11-04: last of 4 revisions
2011-06-17: received
See all versions
Short URL
https://ia.cr/2011/327
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/327,
      author = {Eyal Kushilevitz and Steve Lu and Rafail Ostrovsky},
      title = {On the (In)security of Hash-based Oblivious RAM and a New Balancing Scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2011/327},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/327}},
      url = {https://eprint.iacr.org/2011/327}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.