Paper 2011/407

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

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

Abstract

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Keywords
Oblivious RAMworst-case cost
Contact author(s)
elaines @ eecs berkeley edu
History
2011-11-29: last of 7 revisions
2011-07-30: received
See all versions
Short URL
https://ia.cr/2011/407
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/407,
      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{https://eprint.iacr.org/2011/407}},
      url = {https://eprint.iacr.org/2011/407}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.