Asymptotically Tight Bounds for Composing ORAM with PIR
Asymptotically Tight Bounds for Composing ORAM with PIR
复制标题
用 PIR 组合 ORAM 的渐近紧界
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Ling Ren
中科院分区：
文献类型：
--
作者：
Ittai Abraham;Christopher W. Fletcher;Kartik Nayak;Benny Pinkas;Ling Ren
Oblivious RAM (ORAM) 是一种加密原语，允许受信任的客户端将存储外包给不受信任的服务器，同时向服务器隐藏客户端的内存访问模式。过去三十年对 ORAM 的研究已将 ORAM 方案的带宽爆炸从 (O(sqrt{N})) 减少到 O(1)。然而，所有实现小于 (O(log N)) 的带宽爆炸的方案都使用昂贵的计算，例如同态加密。在本文中，我们在不使用昂贵的计算的情况下实现了 (O(log _{d} N)) 的亚对数带宽爆炸（其中 d 是自由参数）。我们通过使用 d-ary 树和基于服务器上廉价的 XOR 操作的双服务器私有信息检索 (PIR) 协议来实现这一点。我们还展示了涉及 PIR 操作的修改模型中带宽爆炸的 (varOmega (log _{cD} N)) 下限。这里，c是客户端存储的块的数量，D是执行PIR操作的块的数量。我们的构造与该下限相匹配，这意味着下限对于某些参数范围是严格的。最后，我们证明 C-ORAM (CCS 15) 和 CHf-ORAM 违反了下限。结合对C-ORAM/CHf-ORAM的具体攻击，我们认为这些结构存在安全缺陷。
Oblivious RAM (ORAM) is a cryptographic primitive that allows a trusted client to outsource storage to an untrusted server while hiding the client’s memory access patterns to the server. The last three decades of research on ORAMs have reduced the bandwidth blowup of ORAM schemes from (O(sqrt{N})) to O(1). However, all schemes that achieve a bandwidth blowup smaller than (O(log N)) use expensive computations such as homomorphic encryptions. In this paper, we achieve a sub-logarithmic bandwidth blowup of (O(log _{d} N)) (where d is a free parameter) without using expensive computation. We do so by using a d-ary tree and a two server private information retrieval (PIR) protocol based on inexpensive XOR operations at the servers. We also show a (varOmega (log _{cD} N)) lower bound on bandwidth blowup in the modified model involving PIR operations. Here, c is the number of blocks stored by the client and D is the number blocks on which PIR operations are performed. Our construction matches this lower bound implying that the lower bound is tight for certain parameter ranges. Finally, we show that C-ORAM (CCS 15) and CHf-ORAM violate the lower bound. Combined with concrete attacks on C-ORAM/CHf-ORAM, we claim that there exist security flaws in these constructions.