Circuit ORAM: On tightness of the Goldreich-Ostrovsky

Xiao Wang, T. H.Hubert Chan, Elaine Shi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

45 Scopus citations

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 performance and show that Circuit ORAM is an ideal candidate for secure multi-party computation applications.

Original languageEnglish (US)
Title of host publicationCCS 2015 - Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security
PublisherAssociation for Computing Machinery
Pages850-861
Number of pages12
ISBN (Electronic)9781450338325
DOIs
StatePublished - Oct 12 2015
Event22nd ACM SIGSAC Conference on Computer and Communications Security, CCS 2015 - Denver, United States
Duration: Oct 12 2015Oct 16 2015

Publication series

NameProceedings of the ACM Conference on Computer and Communications Security
Volume2015-October
ISSN (Print)1543-7221

Conference

Conference22nd ACM SIGSAC Conference on Computer and Communications Security, CCS 2015
CountryUnited States
CityDenver
Period10/12/1510/16/15

    Fingerprint

Keywords

  • Oblivious RAM
  • Secure Computation

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications

Cite this

Wang, X., Chan, T. H. H., & Shi, E. (2015). Circuit ORAM: On tightness of the Goldreich-Ostrovsky. In CCS 2015 - Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security (pp. 850-861). (Proceedings of the ACM Conference on Computer and Communications Security; Vol. 2015-October). Association for Computing Machinery. https://doi.org/10.1145/2810103.2813634