Practicing Oblivious Access on Cloud Storage: the Gap, the Fallacy, and the New Way Forward

www.oblivious-storage.com To understand the gap between theory and practice for obliv-ious cloud storage, we experimentally evaluate four repre-sentative Oblivious RAM (ORAM) designs on Amazon S3. We replay realistic application traces to these ORAMs in order to understand whether they can meet the demands of various real applications using cloud storage as a backend. We find that metrics traditionally used in the ORAM litera-ture, e.g., bandwidth overhead, fail to capture the practical needs of those applications. With a new understanding of the desirable properties, relevant metrics, and observations about the cloud services and their applications, we propose CURIOUS, a new modular partition-based ORAM frame-work, and show experimentally that it is thus far the most promising approach