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$
$\endgroup$
3
-
$\begingroup$ This "theorem" is in the introduction, and is labeled "informal statement". Have you read the rest of the paper? (I haven't.) $\endgroup$– fkraiemMay 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 LeoMay 4, 2015 at 12:40
-
$\begingroup$ I would guess that the proof would be in Ostrovsky's PhD thesis. $\endgroup$– mikeazoMay 4, 2015 at 20:14
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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:
-
$\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 LeoMay 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 LeoMay 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