# Optimal bandwidth cost for Oblivious RAM

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?

• This "theorem" is in the introduction, and is labeled "informal statement". Have you read the rest of the paper? (I haven't.) – fkraiem May 4 '15 at 10:21
• 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. – Jan Leo May 4 '15 at 12:40
• I would guess that the proof would be in Ostrovsky's PhD thesis. – mikeazo May 4 '15 at 20:14

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):

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:

• 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 – Jan Leo May 5 '15 at 7:54
• 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$) – Daniel Apon May 8 '15 at 1:09
• 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? – Jan Leo May 9 '15 at 19:10
• 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! – Daniel Apon May 12 '15 at 2:52