Cryptology ePrint Archive: Report 2014/732

Resizable Tree-Based Oblivious RAM

Tarik Moataz and Travis Mayberry and Erik-Oliver Blass and Agnes Hui Chan

Abstract: Although newly proposed, tree-based Oblivious RAM schemes are drastically more efficient than older techniques, they come with a significant drawback: an inherent dependence on a fixed-size database. This capability is vital for real-world use of Oblivious RAM since one of its most promising deployment scenarios is for cloud storage, where scalability and elasticity are crucial. We revisit the original construction by Shi et al. [16] and propose several ways to support both increasing and decreasing the ORAMís size with sublinear communication. We show that increasing capacity can be accomplished by adding leaf nodes to the tree, but that it must be done carefully in order to preserve the probabilistic integrity of the data structures. We also provide new, tighter bounds for the size of interior and leaf nodes in the scheme, saving bandwidth and storage over previous constructions. Finally, we define an oblivious pruning technique for removing leaf nodes and decreasing the size of the tree. We show that this pruning method is both secure and efficient.

Category / Keywords: cryptographic protocols / Oblivious RAM

Original Publication (in the same form): Financial Cryptography and Data Security 2015

Date: received 19 Sep 2014, last revised 8 Dec 2014

Contact author: tmoataz at cs colostate edu

Available format(s): PDF | BibTeX Citation

Version: 20141208:205451 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]