Circuit ORAM: On tightness of the Goldreich-Ostrovsky

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

doi:10.1145/2810103.2813634

Circuit ORAM: On tightness of the Goldreich-Ostrovsky

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

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	CCS 2015 - Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security
Publisher	Association for Computing Machinery
Pages	850-861
Number of pages	12
ISBN (Electronic)	9781450338325
DOIs	https://doi.org/10.1145/2810103.2813634
State	Published - Oct 12 2015
Event	22nd ACM SIGSAC Conference on Computer and Communications Security, CCS 2015 - Denver, United States Duration: Oct 12 2015 → Oct 16 2015

Publication series

Name	Proceedings of the ACM Conference on Computer and Communications Security
Volume	2015-October
ISSN (Print)	1543-7221

Conference

Conference	22nd ACM SIGSAC Conference on Computer and Communications Security, CCS 2015
Country	United States
City	Denver
Period	10/12/15 → 10/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

@inproceedings{73ba45aae30840b891e0dac952bb399e,

title = "Circuit ORAM: On tightness of the Goldreich-Ostrovsky",

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.",

keywords = "Oblivious RAM, Secure Computation",

author = "Xiao Wang and Chan, {T. H.Hubert} and Elaine Shi",

year = "2015",

month = oct

day = "12",

doi = "10.1145/2810103.2813634",

language = "English (US)",

series = "Proceedings of the ACM Conference on Computer and Communications Security",

publisher = "Association for Computing Machinery",

pages = "850--861",

booktitle = "CCS 2015 - Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security",

note = "22nd ACM SIGSAC Conference on Computer and Communications Security, CCS 2015 ; Conference date: 12-10-2015 Through 16-10-2015",

}

Wang, X, Chan, THH & 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. Proceedings of the ACM Conference on Computer and Communications Security, vol. 2015-October, Association for Computing Machinery, pp. 850-861, 22nd ACM SIGSAC Conference on Computer and Communications Security, CCS 2015, Denver, United States, 10/12/15. https://doi.org/10.1145/2810103.2813634

Circuit ORAM : On tightness of the Goldreich-Ostrovsky. / Wang, Xiao; Chan, T. H.Hubert; Shi, Elaine.

CCS 2015 - Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security. Association for Computing Machinery, 2015. p. 850-861 (Proceedings of the ACM Conference on Computer and Communications Security; Vol. 2015-October).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Circuit ORAM

T2 - 22nd ACM SIGSAC Conference on Computer and Communications Security, CCS 2015

AU - Wang, Xiao

AU - Chan, T. H.Hubert

AU - Shi, Elaine

PY - 2015/10/12

Y1 - 2015/10/12

N2 - 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.

AB - 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.

KW - Oblivious RAM

KW - Secure Computation

UR - http://www.scopus.com/inward/record.url?scp=84954166063&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84954166063&partnerID=8YFLogxK

U2 - 10.1145/2810103.2813634

DO - 10.1145/2810103.2813634

M3 - Conference contribution

AN - SCOPUS:84954166063

T3 - Proceedings of the ACM Conference on Computer and Communications Security

SP - 850

EP - 861

BT - CCS 2015 - Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security

PB - Association for Computing Machinery

Y2 - 12 October 2015 through 16 October 2015

ER -

Access to Document

10.1145/2810103.2813634