Recursive Trees for Practical ORAM
Recursive Trees for Practical ORAM
复制标题
实用 ORAM 的递归树
DOI：
--
复制
发表时间：
2015
影响因子：
--
通讯作者：
G. Noubir
中科院分区：
文献类型：
--
作者：
Tarik Moataz;Erik;G. Noubir
摘要：我们提出了一种新的通用数据结构，可以降低最近基于树的 ORAM 的通信成本。与具有恒定高度和路径长度的 ORAM 树相反，我们的新结构 r-ORAM 允许树具有不同的较短路径长度。访问 ORAM 树中的元素会导致不同的通信成本，具体取决于元素的位置。 r-ORAM 背后的主要思想是递归 ORAM 树结构，其中树中的节点是其他树的根。虽然这种方法最多会导致最坏情况的访问成本（树高度）与任何最近的基于树的 ORAM 一样，但我们表明，对于最近的二叉树 ORAM，平均成本节省约为 35%。除了降低通信成本之外，r-ORAM 还可以将服务器上的存储开销降低 4% 到 20%，具体取决于 ORAM 的客户端内存类型。为了证明 r-ORAM 的可靠性，我们进行了详细的溢出分析。 r-ORAM 的递归方法是通用的，因为它可以应用于所有最近的树 ORAM，包括常量和多对数客户端内存 ORAM。最后，我们在实际环境中实现 r-ORAM 并对其进行基准测试，以支持我们的理论主张。
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.