Paper 2011/407 Original: eprint.iacr.org/2011/407 ↗
Oblivious RAM with O((log N)^3) Worst-Case Cost
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
- Preprint.
- History
- 2011-11-29: last updated
- 2011-07-30: published
- Short URL
- https://ia.cr/2011/407
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}