Paper 2014/603

Recursive Trees for Practical ORAM

Tarik Moataz, Erik-Oliver Blass, and Guevara Noubir


We present a new, general data structure that reduces the communication cost of recent tree-based ORAMs. Contrary to ORAM trees with constant height and path lengths, our new construction r-ORAM allows for trees with varying shorter path length. Accessing an element in the ORAM tree results in different communication costs depending on the location of the element. The main idea behind r-ORAM is a recursive ORAM tree structure, where nodes in the tree are roots of other trees. While this approach results in a worst-case access cost (tree height) at most as any recent tree-based ORAM, we show that the average cost saving is around 35% for recent binary tree ORAMs. Besides reducing communication cost, r-ORAM also reduces storage overhead on the server by 4% to 20% depending on the ORAM's client memory type. To prove r-ORAM's soundness, we conduct a detailed overflow analysis. r-ORAM's recursive approach is general in that it can be applied to all recent tree ORAMs, both constant and poly-log client memory ORAMs. Finally, we implement and benchmark r-ORAM in a practical setting to back up our theoretical claims.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. PETS 2015
Oblivious RAM
Contact author(s)
tmoataz @ cs colostate edu
2015-08-14: last of 2 revisions
2014-08-11: received
See all versions
Short URL
Creative Commons Attribution


      author = {Tarik Moataz and Erik-Oliver Blass and Guevara Noubir},
      title = {Recursive Trees for Practical ORAM},
      howpublished = {Cryptology ePrint Archive, Paper 2014/603},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.