On the (In)security of Hash-Based Oblivious RAM and a New Balancing Scheme
With the gaining popularity of remote storage (e.g. in the Cloud), the authors consider the setting where a small, protected local machine wishes to access data on a large, untrusted remote machine. This setting was introduced in the RAM model in the context of software protection by Goldreich and Ostrovsky. A secure Oblivious RAM simulation allows for a client, with small (e.g. constant) size protected memory, to hide not only the data nut also the sequence of locations it accesses (both reads and writes) in the unprotected memory of size n.