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
-
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},
url = {https://eprint.iacr.org/2011/407}
}
