Perfectly Secure Oblivious RAM with Sublinear Bandwidth Overhead
Perfectly Secure Oblivious RAM with Sublinear Bandwidth Overhead
复制标题
具有次线性带宽开销的完美安全 Oblivious RAM
DOI：
10.1007/978-3-030-34621-8_19
复制
发表时间：
2019
影响因子：
5
通讯作者：
Mark Simkin
中科院分区：
文献类型：
--
作者：
Michael A. Raskin;Mark Simkin
无关RAM （ORAM）已经确立了自己作为基本加密构建块的地位。了解哪些带宽开销在哪些假设下是可能的，这是以前大量工作的主题。在这项工作中，我们专注于完全安全的ORAM，并提出了在最坏情况下具有次线性带宽开销的第一个结构。所有具有完美安全性的先前结构在最坏情况下都需要线性通信开销，并且只能实现平摊意义上的亚线性带宽开销。我们提出了一种全新的构建ORAM的方法，我们的结果大大提高了我们对完美安全性的理解。
Oblivious RAM (ORAM) has established itself as a fundamental cryptographic building block. Understanding which bandwidth overheads are possible under which assumptions has been the topic of a vast amount of previous works. In this work, we focus on perfectly secure ORAM and we present the first construction with sublinear bandwidth overhead in the worst-case. All prior constructions with perfect security require linear communication overhead in the worst-case and only achieve sublinear bandwidth overheads in the amortized sense. We present a fundamentally new approach for constructing ORAM and our results significantly advance our understanding of what is possible with perfect security.