Abstract:

When storing data at an untrusted server, one can hide the contents by encrypting it. But still the access pattern to the data might reveal some information. An oblivious RAM (ORAM) is a protocol for implementing a RAM functionality leaking only the size of the stored data given a constant-size local memory and access to an external RAM that leaks the access pattern. In this talk we study the problem of ORAM, and present an algorithm for implementing a secure ORAM where the access pattern is perfectly hidden in the information theoretic sense, without assuming that the CPU has access to a random oracle or other cryptographic primitives.