Paper 2016/849

Asymptotically Tight Bounds for Composing ORAM with PIR

Ittai Abraham, Christopher W. Fletcher, Kartik Nayak, Benny Pinkas, and Ling Ren

Abstract

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 $\Omega(\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.

Note: This extends our original submission with a lower bound on ORAMs using PIR and shows two attacks on C-ORAM/CHf-ORAM.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in Pkc 2017
Keywords
Oblivious RAMPIRlower bound
Contact author(s)
kartik @ cs umd edu
History
2017-01-17: last of 2 revisions
2016-09-07: received
See all versions
Short URL
https://ia.cr/2016/849
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/849,
      author = {Ittai Abraham and Christopher W.  Fletcher and Kartik Nayak and Benny Pinkas and Ling Ren},
      title = {Asymptotically Tight Bounds for Composing ORAM with PIR},
      howpublished = {Cryptology ePrint Archive, Paper 2016/849},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/849}},
      url = {https://eprint.iacr.org/2016/849}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.