Recursive Trees for Practical ORAM
Authors: Tarik Moataz (Dept. of Computer Science, Colorado State University, Fort Collins, CO , and IMT, Telecom Bretagne, France), Erik-Oliver Blass (Airbus Group Innovations, 81663 Munich, Germany), Guevara Noubir (College of Computer and Information Science, Northeastern University, Boston, MA)
Volume: 2015
Issue: 2
Pages: 115–134
DOI: https://doi.org/10.1515/popets-2015-0010
Abstract: We present a new, general data structure that reduces the communication cost of recent treebased 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 worstcase access cost (tree height) at most as any recent treebased 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. rORAM’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.
Keywords: Oblivious RAM, cryptographic protocols
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 license.
