Oblivious RAM

Today's study group was on Oblivious RAM - a concept introduced by Goldreich and Ostrovsky, which enables a client storing only a small amount of data locally to store a large amount of data in e.g the cloud and access them while hiding the identities of the items being accessed.

Roughly speaking the adversary model for Oblivious RAM is as follows - an adversary can't distinguish between equal length sequence of queries made by the client to the server. Early solutions required the server to store O(N*log(N)) data items and each access to a data item actually required O(log^3(N)) data requests. Later work of Pinkas & Reinman brought this down to O(N) storage and O(log^2(N)) requests. However their solution was insecure but an improvement later made this secure. Interestingly there is a theoretical lower bound on the number of requests of log(N). Essentially the overhead arises out of which data oblivious sorting algorithm one chooses.

We focus on the quadratic solution which is conceptually the simplest to understand. In essence we have a memory cell of adressess [0,N] which we expand by an extra sqrt(N) which will hold an extra sqrt(N) dummy data. We also have a "shelter" of size sqrt(N). The first step is to randomly permute all locations [0, N + sqrt(N)] (i.e everything outside the shelter) using a permutation derived from a random oracle. We carry out sqrt(N) memory accesses as follows: previously accessed memory is kept in the sheltered locations. An access to the original RAM works as follows: say we wish to access memory at location i. First we scan through the shelter and check whether the contents of the original memory is held at one of the locations [N+sqrt(N)+1,N+2*sqrt(N)]. If it's not there its at location pi(i) where pi is our permutation. If it is there, we access the next dummy word (i.e if we are on the j'th access for 1<= j <= sqrt(N) we use the dummy at pi(m+j)). For further details see http://dl.acm.org/citation.cfm?id=233553

The significantly more efficient "heirarchical" approach is a lot more involved. The interested reader should consult Goldreich & Ostrovsky paper. Also of interest is the multiparty approach of Damgaard et al. eprint.iacr.org/2010/108.pdf which removes the need for a random oracle.

Jake