LolliRAM: A Cross-Layer Design to Exploit Data Locality in Oblivious RAM

Oblivious RAM (ORAM) conceals memory access pattern by translating a single read/write operation into the accesses to a set of randomized locations. The obliviousness is achieved by adding redundancy to the memory system, which comes at the expense of increased performance overhead. In memory systems, locality has always been a critical factor, as accessing the data with temporal or spatial locality would result in a performance gain. Although the two design considerations of obliviousness and locality may seem contradictory at first glance, combining them in a unified design can potentially hide long memory access latency in ORAM without sacrificing provable data security. This paper presents LolliRAM, a cross-layer design to exploit data locality in Oblivious RAM. LolliRAM optimizes ORAM system through two different layers: (i) the data structure in ORAM, and (ii) the fast and secure cache in ORAM controller. The reuse of redundant memory accesses at the layer of data structure in ORAM can effectively reduce memory footprints. Both temporal and spatial locality can be exploited through the elastic grouping of blocks and the optimization at the layer of ORAM controller. We conduct a set of experiments using realistic workloads that are generated from standard benchmarks. Experimental results show that LolliRAM can reduce access latency by 71.57% on average (up to 81.50%) with negligible space overhead in comparison with representative schemes.