Paper 2011/407

Oblivious RAM with O((log N)^3) Worst-Case Cost

Elaine Shi, Hubert Chan, Emil Stefanov, and Mingfei Li


Oblivious RAM (O-RAM) is a useful primitive that allows a client to hide its data access patterns from an untrusted server in storage outsourcing applications. This paper proposes novel O-RAM constructions that achieves poly-logarithmic worst-case cost, while consuming constant client-side storage. Our techniques for constructing Oblivious RAM are fundamentally different from previous approaches. Specifically, we organize the O-RAM storage into a binary tree over data buckets, while moving data blocks obliviously along tree edges. Our construction (instantiated the trivial bucket O-RAM) has remarkable conceptual simplicity, and eliminates the need to perform expensive oblivious sorting operations. As a result, to the best of our knowledge, our construction is by far the most practical scheme with constant client-side memory, under realistic parameterizations.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Oblivious RAMworst-case cost
Contact author(s)
elaines @ eecs berkeley edu
2011-11-29: last of 7 revisions
2011-07-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Elaine Shi and Hubert Chan and Emil Stefanov and Mingfei Li},
      title = {Oblivious RAM with O((log N)^3) Worst-Case Cost},
      howpublished = {Cryptology ePrint Archive, Paper 2011/407},
      year = {2011},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.