Paper 2014/205

Unified Oblivious-RAM: Improving Recursive ORAM with Locality and Pseudorandomness

Ling Ren, Christopher Fletcher, Xiangyao Yu, Albert Kwon, Marten van Dijk, and Srinivas Devadas

Abstract

Oblivious RAM (ORAM) is a cryptographic primitive that hides memory access patterns to untrusted storage. ORAM may be used in secure processors for encrypted computation and/or software protection. While recursive Path ORAM is currently the most practical ORAM for secure processors, it still incurs large performance and energy overhead and is the performance bottleneck of recently proposed secure processors. In this paper, we propose two optimizations to recursive Path ORAM. First, we identify a type of program locality in its operations to improve performance. Second, we use pseudorandom function to compress the position map. But applying these two techniques in recursive Path ORAM breaks ORAM security. To securely take advantage of the two ideas, we propose unified ORAM. Unified ORAM improves performance both asymptotically and empirically. Empirically, our experiments show that unified ORAM reduces data movement from ORAM by half and improves benchmark performance by 61% as compared to recursive Path ORAM.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. Minor revision.
Keywords
Oblivious Ramaccess patternlocalitypseudorandomness
Contact author(s)
renling @ mit edu
History
2014-06-04: revised
2014-03-20: received
See all versions
Short URL
https://ia.cr/2014/205
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/205,
      author = {Ling Ren and Christopher Fletcher and Xiangyao Yu and Albert Kwon and Marten van Dijk and Srinivas Devadas},
      title = {Unified Oblivious-RAM: Improving Recursive ORAM with Locality and Pseudorandomness},
      howpublished = {Cryptology ePrint Archive, Paper 2014/205},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/205}},
      url = {https://eprint.iacr.org/2014/205}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.