Cryptology ePrint Archive: Report 2014/603

Recursive Trees for Practical ORAM

Tarik Moataz and Erik-Oliver Blass and Guevara Noubir

Abstract: 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.

Category / Keywords: cryptographic protocols / Oblivious RAM

Original Publication (in the same form): PETS 2015

Date: received 5 Aug 2014, last revised 14 Aug 2015

Contact author: tmoataz at cs colostate edu

Available format(s): PDF | BibTeX Citation

Version: 20150814:192500 (All versions of this report)

Short URL: ia.cr/2014/603

Discussion forum: Show discussion | Start new discussion