Paper 2013/239

Optimizing ORAM and Using it Efficiently for Secure Computation

Craig Gentry, Kenny Goldman, Shai Halevi, Charanjit Julta, Mariana Raykova, and Daniel Wichs

Abstract

Oblivious RAM (ORAM) allows a client to access her data on a remote server while hiding the access pattern (which locations she is accessing) from the server. Beyond its immediate utility in allowing private computation over a client's outsourced data, ORAM also allows mutually distrustful parties to run secure-computations over their joint data with sublinear on-line complexity. In this work we revisit the tree-based ORAM of Shi et al. [SCSL11] and show how to optimize its performance as a stand-alone scheme, as well as its performance within higher level constructions. More specifically, we make several contributions: - We describe two optimizations to the tree-based ORAM protocol of Shi et al., one reducing the storage overhead of that protocol by an $O(k)$ multiplicative factor, and another reducing its time complexity by an $O(\log k)$ multiplicative factor, where $k$ is the security parameter. Our scheme also enjoys a much simpler and tighter analysis than the original protocol. - We describe a protocol for binary search over this ORAM construction, where the entire binary search operation is done in the same complexity as a single ORAM access (as opposed to $\log n$ accesses for the naive protocol). We then describe simple uses of this binary-search protocol for things like range queries and keyword search. - We show how the ORAM protocol itself and our binary-search protocol can be implemented efficiently as secure computation, using somewhat-homomorphic encryption. Since memory accesses by address (ORAM access) or by value (binary search) are basic and prevalent operations, we believe that these optimizations can be used to significantly speed-up many higher-level protocols for secure computation.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Full version of a PETS (privacy-enhancing technologies) 2013 paper.
Keywords
oblivious RAM
Contact author(s)
wichs @ ccs neu edu
History
2013-04-29: received
Short URL
https://ia.cr/2013/239
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/239,
      author = {Craig Gentry and Kenny Goldman and Shai Halevi and Charanjit Julta and Mariana Raykova and Daniel Wichs},
      title = {Optimizing ORAM and Using it Efficiently for Secure Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2013/239},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/239}},
      url = {https://eprint.iacr.org/2013/239}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.