Resizable Tree-Based Oblivious RAM
Resizable Tree-Based Oblivious RAM
复制标题
可调整大小的基于树的遗忘 RAM
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
A. Chan
中科院分区：
文献类型：
--
作者：
Tarik Moataz;Travis Mayberry;Erik;A. Chan
虽然新提出的基于树的不经意RAM方案比旧技术效率高得多，但它们有一个显著的缺点：对固定大小数据库的固有依赖。然而，灵活的存储对于现实世界中使用不经意RAM至关重要，因为其最有前途的部署场景之一是云存储，其中可扩展性和弹性至关重要。我们重新审视了Shi等人的原始构造。[17]并提出了几种方法来支持使用次线性通信增加和减少ORAM的大小。我们表明，增加容量可以通过添加叶节点的树，但它必须仔细做，以保持数据结构的概率完整性。我们还提供了新的，更严格的边界的内部和叶节点的大小在该计划中，节省带宽和存储在以前的建设。最后，我们定义了一个不经意的修剪技术，删除叶节点，减少树的大小。我们表明，这种修剪方法是安全和有效的。
Although newly proposed, tree-based Oblivious RAM schemes are drastically more efficient than older techniques, they come with a significant drawback: an inherent dependence on a fixed-size database. Yet, a flexible storage is vital for real-world use of Oblivious RAM since one of its most promising deployment scenarios is for cloud storage, where scalability and elasticity are crucial. We revisit the original construction by Shi et al. [17] and propose several ways to support both increasing and decreasing the ORAM’s size with sublinear communication. We show that increasing the capacity can be accomplished by adding leaf nodes to the tree, but that it must be done carefully in order to preserve the probabilistic integrity of data structures. We also provide new, tighter bounds for the size of interior and leaf nodes in the scheme, saving bandwidth and storage over previous constructions. Finally, we define an oblivious pruning technique for removing leaf nodes and decreasing the size of the tree. We show that this pruning method is both secure and efficient.