Cryptology ePrint Archive: Report 2014/603

Recursive Trees for Practical ORAM

Tarik Moataz and Erik-Oliver Blass and Guevara Noubir

Abstract: We present a general construction to reduce the communication cost of recent tree-based ORAMs. Contrary to trees with constant height and path lengths, our new construction r-ORAM provides varying, shorter path lengths. Accessing an element in the ORAM tree will have different communication cost 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 demonstrate that the expected cost saving is around 35% for binary tree ORAMs. For a k-ary tree-based ORAM, we still can reduce cost with r-ORAM, e.g., 20% for k =4. Besides reducing communication cost, r-ORAM also reduces storage overhead on the server by 20%. To prove r-ORAMís soundness, we conduct a detailed overflow analysis. We stress that r-ORAM is general and can be applied to all recent tree ORAMs, both constant memory or poly-log client memory ORAMs.

Category / Keywords: cryptographic protocols / Oblivious RAM

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

Contact author: tmoataz at cs colostate edu

Available format(s): PDF | BibTeX Citation

Version: 20140811:123434 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]