@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",
note = "Funding Information: This research was funded in part by NSF grants CNS-1314857, CNS-1453634, CNS-1518765, CNS-1514261, a subcontract from the DARPA PROCEED program, a Sloan Research Fellowship, a Google Faculty Research Award and a grant from Hong Kong RGC under the contract HKU719312E. We gratefully acknowledge Bill Gasarch, Mor Harchol-Balter, Dov Gordon, Clyde Kruskal, Kartik Nayak, Charalampos Papamanthou, and abhi shelat for helpful discussions. Publisher Copyright: {\textcopyright} 2015 ACM.; 22nd ACM SIGSAC Conference on Computer and Communications Security, CCS 2015 ; Conference date: 12-10-2015 Through 16-10-2015",
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",
}