rORAM: Efficient Range ORAM with O(log2 N) Locality

Abstract

Oblivious RAM protocols (ORAMs) allow a client to access data from an untrusted storage device without revealing to that device any information about their access pattern. Typically this is accomplished through random shuffling of the data such that the storage device cannot determine where individual blocks are located, resulting in a highly randomized access pattern. Storage devices however, are typically optimized for sequential access. A large number of random disk seeks during standard ORAM operation induce a substantial overhead.