Oblivious RAM with Small Storage Overhead
In this work, we present a new approach to constructing Oblivious RAM (ORAM) Somewhat surprisingly, and despite the large amount of research interest that ORAM has received, all existing ORAM constructions are based on a handful of conceptually different approaches. We believe it is of theoretical and practical interest to explore new ways to construct this primitive. Our first construction is conceptually extremely simple and has a worst case bandwidth overhead of O N logN log logN where N is the number of data blocks. Our main construction, Lookahead ORAM, has a worst case bandwidth overhead of O N and an additive storage overhead of 2N which is the smallest concrete storage overhead among all existing ORAM constructions with sublinear worst case bandwidth overhead. A small storage overhead is particularly beneficial in outsourced storage settings, where data owners have to pay their storage provider for the amount of storage they consume. In addition to having a small storage overhead, Lookahead ORAM has perfect correctness, i.e. every operation on the ORAM data structure succeeds with probability 1 and, assuming the client stores some small stash of data locally, an online bandwidth overhead of O (1) without server side computation. In comparison with prior work that has sublinear worst case bandwidth overhead, Lookahead ORAM is asymptotically the most efficient ORAM with perfect correctness.
IACR Cryptol. ePrint Arch.