Cryptology ePrint Archive: Report 2011/407

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

Elaine Shi, Hubert Chan, Emil Stefanov, 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.

Category / Keywords: cryptographic protocols / Oblivious RAM, worst-case cost

Date: received 29 Jul 2011, last revised 28 Nov 2011

Contact author: elaines at eecs berkeley edu

Available format(s): PDF | BibTeX Citation

Version: 20111129:051758 (All versions of this report)

Short URL: ia.cr/2011/407

Discussion forum: Show discussion | Start new discussion