Perfectly Secure Oblivious Parallel RAM
Perfectly Secure Oblivious Parallel RAM
复制标题
完全安全的遗忘并行 RAM
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
E. Shi
中科院分区：
文献类型：
--
作者：
T;Kartik Nayak;E. Shi
我们证明了PRAM可以被完全安全地遗忘模拟，仅在并行运行时发生（O（log N log log N））爆炸，在总工作中发生（O（log ^3 N））爆炸，并且相对于原始PRAM在空间上发生O（1）爆炸。我们的研究结果在几个方面推进了对不经意（并行）RAM的理论理解。首先，在我们的工作之前，没有完全安全的不经意并行RAM（OPRAM）结构是已知的，我们是第一个在这方面。其次，即使对于我们算法的顺序特殊情况（即，完全安全的ORAM），我们不仅相对于现有技术在空间消耗方面实现了对数改进，而且还显著简化了完全安全的ORAM构造。第三，我们完全安全的OPRAM计划相匹配的并行运行时间的早期统计安全的计划可以忽略不计的失败概率。由于我们删除的依赖（在性能上）的安全参数，我们完全安全的OPRAM计划实际上渐近优于已知的统计安全的，如果（子）指数小的故障概率是理想的。我们的技术，实现小并行运行时是新颖的，我们采用特殊的扩展图去随机化早期统计安全的OPRAM技术，这是第一次这样的技术被用于在建设的ORAMs/OPRAM。
We show that PRAMs can be obliviously simulated with perfect security, incurring only (O(log N log log N)) blowup in parallel runtime, (O(log ^3 N)) blowup in total work, and O(1) blowup in space relative to the original PRAM. Our results advance the theoretical understanding of Oblivious (Parallel) RAM in several respects. First, prior to our work, no perfectly secure Oblivious Parallel RAM (OPRAM) construction was known; and we are the first in this respect. Second, even for the sequential special case of our algorithm (i.e., perfectly secure ORAM), we not only achieve logarithmic improvement in terms of space consumption relative to the state-of-the-art, but also significantly simplify perfectly secure ORAM constructions. Third, our perfectly secure OPRAM scheme matches the parallel runtime of earlier statistically secure schemes with negligible failure probability. Since we remove the dependence (in performance) on the security parameter, our perfectly secure OPRAM scheme in fact asymptotically outperforms known statistically secure ones if (sub-)exponentially small failure probability is desired. Our techniques for achieving small parallel runtime are novel and we employ special expander graphs to derandomize earlier statistically secure OPRAM techniques—this is the first time such techniques are used in the constructions of ORAMs/OPRAMs.