Perfectly Secure Oblivious RAM Without Random Oracles
Source: University of Aarhus
In many cases it is attractive to store data at an untrusted party, and only retrieve the needed parts of it. Encryption can help ensure that the party storing the data has no idea of what he is storing, but still it is possible to get information about the stored data by analyzing the access pattern. A trivial solution is to access all data every time one piece of data is needed. However, many algorithms are designed for being effective in the RAM-model, where access to any word of the memory takes constant time, and so accessing all data for every data access gives an overhead that is linear in the size of the used memory.