Statistically-secure ORAM with Õ(log2 n) Overhead
Statistically-secure ORAM with Õ(log2 n) Overhead
复制标题
具有 Õ(log2 n) 开销的统计安全 ORAM
DOI：
10.1007/978-3-662-45608-8_4
复制
发表时间：
2013
影响因子：
0.3
通讯作者：
R. Pass
中科院分区：
文献类型：
--
作者：
Kai;Zhenming Liu;R. Pass
我们证明了一个简单的，统计的oram，具有计算开销〜O（log 2 n）；概念上的简单性，使其易于在软件和（商业上）的硬件中实现。 Li（Asiacrypt 2011）和Stefanov and Shi（Arxiv 2012），但是在算法中进行了一些关键的修改，可以简化Oram并启用我们的分析中的中心部分。问题;我们的兴趣（对我们的分析很重要），我们在“超市”问题中提供了“沮丧”客户的上限。
We demonstrate a simple, statistically secure, ORAM with computational overhead ~ O(log 2 n); previous ORAM protocols achieve only computational security (under computational assumptions) or require ~ (log 3 n) overheard. An additional benefit of our ORAM is its conceptual simplicity, which makes it easy to implement in both software and (commercially available) hardware. Our construction is based on recent ORAM constructions due to Shi, Chan, Stefanov, and Li (Asiacrypt 2011) and Stefanov and Shi (ArXiv 2012), but with some crucial modifications in the algorithm that simplifies the ORAM and enable our analysis. A central component in our analysis is reducing the analysis of our algorithm to a “supermarket” problem; of independent interest (and of importance to our analysis,) we provide an upper bound on the rate of “upset” customers in the “supermarket” problem.