Remote Oblivious Storage: Making Oblivious RAM Practical
Remote storage of data has become an increasingly attractive and advantageous option, especially due to cloud systems. While encryption protects the data, it does not hide the access pattern to the data. A natural solution is to access remote storage using an Oblivious RAM (ORAM) which provably hides all access patterns. While ORAM is asymptotically efficient, the best existing scheme (Pinkas and Reinman, Crypto'10) still has considerable overhead for a practical implementation: for M stored items, it stores 4 times and sometimes 6 times more items remotely, requires O(log2M) round trips to storage server per request, and periodically blocks all data requests to shuffle all storage (which is a lengthy process).