Implementing and Analyzing a Recursive Technique for Building Path Oblivious RAM

It has been demonstrated that encrypting confidential data before storing it is not sufficient because data access patterns can leak significant information about the data itself (Goldreich & Ostrovsky, 1996). Oblivious RAM (ORAM) schemes exist in order to protect the access pattern of data in a data-store. Under an ORAM algorithm, a client accesses a data store in such a way that does not reveal which item it is interested in. This is typically accomplished by accessing multiple items each access and periodically reshuffling some, or all, of the data on the data-store. One critical limitation of ORAM techniques is the need to have large storage capacity on the client, which is typically a weak device. In this work, we utilize an ORAM technique that adapts itself to working with clients having very limited storage. A trivial implementation for an oblivious RAM scans the entire memory for each actual memory access. This scheme is called linear ORAM. Goldreich and Ostrovsky (Goldreich & Ostrovsky, 1996) pre...