Paper 2014/997

Constants Count: Practical Improvements to Oblivious RAM

Ling Ren, Christopher W. Fletcher, Albert Kwon, Emil Stefanov, Elaine Shi, Marten van Dijk, and Srinivas Devadas

Abstract

Oblivious RAM (ORAM) is a cryptographic primitive that hides memory access patterns as seen by untrusted storage. This paper proposes Ring ORAM, the most bandwidth-efficient ORAM scheme for the small client storage setting in both theory and practice. Ring ORAM is the first tree-based ORAM whose bandwidth is independent of the ORAM bucket size, a property that unlocks multiple performance improvements. First, Ring ORAM’s overall bandwidth is 2.3x to 4x better than Path ORAM, the prior-art scheme for small client storage. Second, if memory can perform simple untrusted computation, Ring ORAM achieves constant online bandwidth (~60x improvement over Path ORAM for practical parameters). As a case study, we show Ring ORAM speeds up program completion time in a secure processor by 1.5x relative to Path ORAM. On the theory side, Ring ORAM features a tighter and significantly simpler analysis than Path ORAM.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. usenix 2015
Contact author(s)
renling @ mit edu
History
2015-07-07: revised
2014-12-18: received
See all versions
Short URL
https://ia.cr/2014/997
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/997,
      author = {Ling Ren and Christopher W.  Fletcher and Albert Kwon and Emil Stefanov and Elaine Shi and Marten van Dijk and Srinivas Devadas},
      title = {Constants Count: Practical Improvements to Oblivious RAM},
      howpublished = {Cryptology ePrint Archive, Paper 2014/997},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/997}},
      url = {https://eprint.iacr.org/2014/997}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.