When storing sensitive data in a third party cloud, users’ access patterns must be hidden from the cloud provider in order to maintain the privacy of the data. Many oblivious RAM (ORAM) systems have been developed for this purpose. However, current proposals are not fault-tolerant.
We present and implement a fault-tolerant ORAM system which allows data to be replicated across multiple cloud providers while maintaining obliviousness and consistency. Our system operates in an asynchronous setting and allows for multiple concurrent readers and writers. Experimental results show that our system has negligible overhead relative to — and in some cases outperforms — non-replicated ORAM.