Could anybody explain me what exactly oblivious RAM is?

I found the following explanation which makes it kind of clear to me, but I would like to get a sense of the technical aspects:

Encryption is not always enough to ensure privacy. If an adversary can observe your access patterns to encrypted storage, they can still learn sensitive information about what your applications are doing. Oblivious RAM solves this problem by continuously shuffling memory as it is being accessed; thereby completely hiding what data is being accessed or even when it was previously accessed.

  • $\begingroup$ What kind of technical aspects? How it's done on the chip? $\endgroup$
    – Raphael
    Nov 25 '14 at 14:29
  • $\begingroup$ I have read that a client needs a particular size of Memory, lets say O(n^1/r) with r > 1, where the server has a memory of size n. My question would be, what happens client-side that the client needs this own memory. $\endgroup$
    – Merlijn
    Nov 25 '14 at 14:40
  • $\begingroup$ Not necessarily, in the ORAM protocol that uses a tree and shifts datapoints down, you can use an idea like L1/L2/L3 caching to offload more memory onto the server so that the client only needs to hold O(1) memory. But without this extension, the client stores a list of indices. $\endgroup$ Feb 17 '17 at 7:47

Oblivious RAM is an interface between a program and the physical RAM that when you perform a read or write, does both at the same time on the physical RAM to hide if you are reading or writing. Plus, it shuffles the memory from time to time so that an adversary seeing only accesses to the physical RAM cannot know whetever you accessed the same data twice or accessed two different data. Thus hiding the access patterns to the physical RAM.

Instantiations I know of rely on oblivious sort, which is a way of sorting elements in a list by comparing and eventually swapping elements in an order predefined, that does not depend on the comparison results.


Your Answer

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

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