This post assumes some knowledge about ORAMs on the reader's part. Very roughly, ORAMs are ways in which one can simulate a generic RAM program for $n$ steps in such a way that the memory access pattern reveals "almost nothing" about the nature of the program or its inputs -- this is orthogonal to hiding the actual contents of the memory itself.

As I was reviewing the related literature, I came into a problem. In many constructions, including the original one by Goldreich and Ostrovsky, security is achieved assuming a) a random oracle and b) O(1) words of memory storage that the adversary cannot access. Furthermore, in many recent constructions, it seems that a) words are assumed to be of size O(lg n) and b) the construction is claimed to fail with at most $1/n^{\omega(1)}$ probability.

But shouldn't this be impossible? In general, random oracles are supposed to be public, i.e. the adversary can query them to obtain your same result if he can guess your seed. Then, If you have O(1) protected words of O(lg n) bits each, an adversary should be able to guess your "protected" state with $1/2^{O(\lg n)}=1/n^{O(1)}$ probability. Am I missing something?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.