Paper 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.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Oblivious RAM
- Contact author(s)
- tmoataz @ cs colostate edu
- History
- 2015-08-14: last of 2 revisions
- 2014-08-11: received
- See all versions
- Short URL
- https://ia.cr/2014/603
- License
-
CC BY