You are looking at a specific version 20140829:231716 of this paper. See the latest version.

Paper 2014/672

Circuit ORAM: On Tightness of the Goldreich-Ostrovsky Lower Bound

Xiao Shaun Wang and T-H. Hubert Chan and Elaine Shi

Abstract

Oblivious RAM (ORAM) constructions have traditionally been measured by their bandwidth cost, or the blowup in the ORAM's running time in comparison with the non-oblivious baseline. While these metrics can suitably characterize an ORAM's performance in secure processor and cloud outsourcing applications, recent works have observed that other applications such as secure multi-party computation demand a different metric, namely, the ORAM's circuit complexity. Following the tree-based ORAM paradigm by Shi et al., we propose a new ORAM scheme called Circuit ORAM. Circuit ORAM achieves $O(D \log N) \omega(1)$ total circuit size\footnote{ We use the notation $g(N) = O(f(N)) \omega(1)$ to denote that for any $\alpha(N) = \omega(1)$, it holds that $g (N) = O(f(N) \alpha(N))$.} (over all protocol interactions) for memory words of $D = \Omega(\log^2 N)$ bits, while achieving a negligible failure probability. For memory words of $D = \Omega(\log^2 N)$ bits, Circuit ORAM achieves smaller circuits both asymptotically and in practice than all previously known ORAM schemes. Empirical results suggest that Circuit ORAM yields circuits that are 8x to 48x smaller than Path ORAM for datasets of roughly 1GB. The speedup will be even greater for larger data sizes. Circuit ORAM is also theoretically interesting when interpreted under the traditional metrics. Parameterizing the scheme slightly differently, we show the following. Let $0 < \epsilon < 1$ denote any constant, and consider a family of RAMs with $N$ words each of which $N^\epsilon$ bits in size. Any RAM in this class can be compiled to an Oblivious RAM with $O(1)$ words of CPU cache, running in $O(T \log N) \omega(1)$ time, and achieving negligible statistical failure probability (or running in $O(T \log N)$ time but with inverse polynomial failure probability). This suggests that certain stronger interpretations of the Goldreich-Ostrovsky ORAM lower bound are tight --- in particular their lower bound trivially generalizes to any $O(1)$ failure probability, and works for arbitrary memory word sizes.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
ORAMsecure computation
Contact author(s)
wangxiao @ cs umd edu
History
2016-11-28: last of 6 revisions
2014-08-29: received
See all versions
Short URL
https://ia.cr/2014/672
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.