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

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.
In this paper, we introduce rORAM, an ORAM specifically suited for
accessing ranges of sequentially logical blocks while minimizing
the number of random physical disk seeks.
rORAM obtains significantly better asymptotic efficiency than prior
designs (Asharov et al., ePrint 2017, Demertzis et al., CRYPTO 2018)
reducing both the number of seeks and communication complexity
by a multiplicative factor of $mathbb{O}(log N)$.
An rORAM prototype is 30-50x times faster than Path ORAM for similar
range-query workloads on local HDDs, 30x faster for local SSDs, and 10x
faster for network block devices.
rORAM's novel disk layout can also speed up standard ORAM constructions,
e.g., resulting in a 2x faster Path ORAM variant. Importantly, experiments demonstrate suitability for real world applications -- rORAM is
up to 5x faster running a file server and up to 11x faster running a range-query intensive video server workloads compared to standard Path ORAM.