Cryptology ePrint Archive: Report 2013/239

Optimizing ORAM and Using it Efficiently for Secure Computation

Craig Gentry and Kenny Goldman and Shai Halevi and Charanjit Julta and 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.

Category / Keywords: cryptographic protocols / oblivious RAM

Publication Info: Full version of a PETS (privacy-enhancing technologies) 2013 paper.

Date: received 28 Apr 2013

Contact author: wichs at ccs neu edu

Available format(s): PDF | BibTeX Citation

Version: 20130429:113625 (All versions of this report)

Short URL: ia.cr/2013/239

Discussion forum: Show discussion | Start new discussion