Paper 2014/672

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

Xiao Wang, Hubert Chan, and Elaine Shi

Abstract

We propose a new tree-based ORAM scheme called Circuit ORAM. Circuit ORAM makes both theoretical and practical contributions. From a theoretical perspective, Circuit ORAM shows that the well-known Goldreich-Ostrovsky logarithmic ORAM lower bound is tight under certain parameter ranges, for several performance metrics. Therefore, we are the first to give an answer to a theoretical challenge that remained open for the past twenty-seven years. Second, Circuit ORAM earns its name because it achieves (almost) optimal circuit size both in theory and in practice for realistic choices of block sizes. We demonstrate compelling practical perfor- mance and show that Circuit ORAM is an ideal candidate for secure multi-party computation applications.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
oblivious RAMsecure multi-party computation
Contact author(s)
runting @ gmail com
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

BibTeX

@misc{cryptoeprint:2014/672,
      author = {Xiao Wang and Hubert Chan and Elaine Shi},
      title = {Circuit ORAM: On Tightness of the Goldreich-Ostrovsky Lower Bound},
      howpublished = {Cryptology ePrint Archive, Paper 2014/672},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/672}},
      url = {https://eprint.iacr.org/2014/672}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.