Paper 2013/280

Path ORAM: An Extremely Simple Oblivious RAM Protocol

Emil Stefanov, Marten van Dijk, Elaine Shi, T-H. Hubert Chan, Christopher Fletcher, Ling Ren, Xiangyao Yu, and Srinivas Devadas

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 = Omega(log^2 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Major revision.CCS 2013
Keywords
oblivious ramoramprivacystorageaccess patterns
Contact author(s)
emil @ cs berkeley edu
History
2014-01-14: revised
2013-05-16: received
See all versions
Short URL
https://ia.cr/2013/280
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/280,
      author = {Emil Stefanov and Marten van Dijk and Elaine Shi and T-H.  Hubert Chan and Christopher Fletcher and Ling Ren and Xiangyao Yu and Srinivas Devadas},
      title = {Path ORAM: An Extremely Simple Oblivious RAM Protocol},
      howpublished = {Cryptology ePrint Archive, Paper 2013/280},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/280}},
      url = {https://eprint.iacr.org/2013/280}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.