@article{1b34a5c88fe34a7897958c9a3335f2c6,
title = "Path ORAM: An extremely simple oblivious RAM protocol",
abstract = "We present Path ORAM, an extremely simple Oblivious RAM protocol with a small amount of client storage. Partly due to its simplicity, Path ORAM is the most practical ORAM scheme known to date with small client storage. We formally prove that Path ORAM has a O(log N) bandwidth cost for blocks of size B = Ω(log2 N) bits. For such block sizes, Path ORAM is asymptotically better than the best-known ORAM schemes with small client storage. Due to its practicality, Path ORAM has been adopted in the design of secure processors since its proposal.",
keywords = "Access pattern, ORAM, Oblivious RAM, Path ORAM",
author = "Emil Stefanov and Dijk, {Marten V.A.N.} and Elaine, {S. H.I.} and Chan, {T. H.Hubert} and Fletcher, {Christopher Wardlaw} and Ling Ren and Xiangyao Yu and Srinivas Devadas",
note = "A conference version of the article has appeared in ACM Conference on Computer and Communications Security (CCS), 2013. This work is partially supported by the NSF Graduate Research Fellowship grants DGE-0946797 and DGE-1122374, the DoD NDSEG Fellowship, NSF grant CNS-1314857, DARPA CRASH program N66001-10-2-4089, and a grant from the Amazon Web Services in Education program. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the funding agencies. The research was supported in part by a grant from Hong Kong RGC under the contract HKU719312E. Authors{\textquoteright} addresses: E. Stefanov, Department of Electrical Engineering and Computer Sciences, UC Berkeley, CA 94720, USA; email:
[email protected]; M. V. Dijk, Electrical and Computing Engineering Department, University of Connecticut, Storrs-Mansfield, CT 06269, USA; email:
[email protected]; E. Shi, Department of Computer Science, Cornell University, Ithaca, NY 14853-7501, USA; email:
[email protected]; T.-H. H. Chan, Department of Computer Science, University of Hong Kong, Pokfulam Road, Hong Kong; email:
[email protected]; C. Fletcher, Computer Science Department, University of Illinois–Urbana Champaign, Urbana, IL 61801, USA; email:
[email protected]; L. Ren, X. Yu, and S. Devadas, MIT CSAIL, Cambridge, MA 02139, USA; emails: {renling, yxy, devadas}@csail.mit.edu. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from
[email protected]. {\textcopyright} 2018 ACM 0004-5411/2018/04-ART18 $15.00 https://doi.org/10.1145/3177872",
year = "2018",
month = apr,
doi = "10.1145/3177872",
language = "English (US)",
volume = "65",
journal = "Journal of the ACM",
issn = "0004-5411",
publisher = "Association for Computing Machinery",
number = "4",
}