ORAM - golemfactory/golem-rd GitHub Wiki
Encryption is not always enough to ensure privacy. Considering that an adversary can observe an access patterns to encrypted storage, they can still learn sensitive information about what the applications are doing. Oblivious RAM solves this problem by continuously shuffling the memory as it is being accessed; thereby completely hiding what data is being accessed or even when it was previously accessed.
An Oblivious RAM is an algorithm at the interface of a protected CPU and the physical RAM that acts like a RAM to the CPU by querying the physical RAM for the CPU and hiding information about the present memory access pattern of the CPU from the physical RAM. Considering that we have two programs that make the same number of memory accesses to the RAM the distribution of memory accesses are indistinguishable from each other.
There have been several attempts recently to increase the efficiency of Oblivious RAM protocols. One of the most successful is Onion ORAM, which achieves $$ O(1) $$ communication overhead with polylogarithmic server computation. However, it has two drawbacks. It requires a large block of the size of $$ B = \Omega(\log^6 N) $$ with large constants. Moreover, while it only needs polylogarithmic computation complexity, that computation consists mostly of expensive homomorphic multiplications.
There are other research proposals cutting down on computational complexity, however, the work is still in progress.
