Goldreich and Ostrovsky show that any ORAM algorithm must have bandwidth cost $\Omega(logN)$, where $N$ is the total number of blocks outsourced. This is in Theorem C of this paper. But they didn't give any proof for this Theorem. Is there other papers that have proved this theorem?

  • $\begingroup$ This "theorem" is in the introduction, and is labeled "informal statement". Have you read the rest of the paper? (I haven't.) $\endgroup$
    – fkraiem
    May 4, 2015 at 10:21
  • $\begingroup$ I went over the paper, but didn't find this theorem appears again. But there is a Theorem in sections 6, which is about the number of steps. $\endgroup$
    – Jan Leo
    May 4, 2015 at 12:40
  • $\begingroup$ I would guess that the proof would be in Ostrovsky's PhD thesis. $\endgroup$
    – mikeazo
    May 4, 2015 at 20:14

1 Answer 1


See Theorem 6, page 38-39..

Also, this lower bound ignores any ability of the "RAM" to perform computation. Typically, there are two application scenarios for ORAM:

1) A literal processor communicating along a literal CPU bus to a literal stick of RAM

2) A client communicating over the internet to a cloud server

In the latter case, it makes sense for the cloud server to provide computational resources to 'speed up' the oblivious simulation. Two works have shown how to achieve $O(1)$ bandwidth overhead (pushing the $\Omega(log(N))$ requisite overhead onto the server's computation instead):

1) http://eprint.iacr.org/2014/153.pdf

2) http://eprint.iacr.org/2015/005.pdf

Also, very recent work based on program obfuscation allows you to implement a "one-shot ORAM," i.e. ORAM with a single round of communication and asymptotically succinct space/time for the server:

1) http://eprint.iacr.org/2015/388.pdf

2) http://eprint.iacr.org/2015/406.pdf

  • $\begingroup$ Thanks, in Theorem 6, they assume m=t, where m is the number of outsourced blocks and t is the number of steps. But what if t is not equal to m, e.g. t is 1? This is another paper that consider server's work: cs.umd.edu/~elaine/docs/burstoram.pdf $\endgroup$
    – Jan Leo
    May 5, 2015 at 7:54
  • $\begingroup$ Ah-- then the lower bound is $|x|$ where $x$ is the input to the RAM. Consider a program that just looks up the value stored in the RAM at index $x\in [N]$. The insecure program makes 1 access, while the ORAM must make $\log(N)$ to be oblivious. And if you have less than $\log(N)$ bits of input, then you can't index all $N$ locations in the memory array anyway. (My $N$ = your $m$) $\endgroup$ May 8, 2015 at 1:09
  • $\begingroup$ OK, that make some sense. But I still would like to ask why need to index all $N$ locations? Suppose there is a ORAM scheme uses only $n<log(N)$ bandwidth. Of course, it can only index at most $2^n$ locations. But If the server cannot figure out where is the $(N-2^n)$ locations, the scheme is still secure, isn't it? $\endgroup$
    – Jan Leo
    May 9, 2015 at 19:10
  • $\begingroup$ This would be kind of like installing 5 gigabytes of RAM in a 32-bit machine. =) But if you can find a good use, go for it! $\endgroup$ May 12, 2015 at 2:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.