Optimizing ORAM and Using It Efficiently for Secure Computation

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. [20] 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.