Paper 2014/732

Resizable Tree-Based Oblivious RAM

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


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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Financial Cryptography and Data Security 2015
Oblivious RAM
Contact author(s)
tmoataz @ cs colostate edu
2014-12-08: revised
2014-09-19: received
See all versions
Short URL
Creative Commons Attribution


      author = {Tarik Moataz and Travis Mayberry and Erik-Oliver Blass and Agnes Hui Chan},
      title = {Resizable Tree-Based Oblivious RAM},
      howpublished = {Cryptology ePrint Archive, Paper 2014/732},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.