A Simple Recursive Tree Oblivious RAM.
Pinkas Benny, Tzachy Reinman · 2014
Oblivious RAM (ORAM) has received increasing attention in the past few years. The goal of obliv-ious RAM is to enable a client, that can locally store only a small (preferably constant) amount of data, to store remotely N data items, and access them while hiding the identities of the items that are be-ing accessed. Most of the earlier ORAM constructions were based on the hierarchical data structure of Goldreich and Ostrovsky [3]. Shi et al. [9] introduced a binary tree ORAM, which is simpler and more efficient than the classical hierarchical ORAM. Gentry et al. [2] have followed them and improved the scheme. In this work, we improve these two constructions. Our scheme asymptotically outper-forms all previous tree based ORAM schemes that have constant client memory, with an overhead of O(log2+N log2 logN) per operation for a O(N) storage server. Although the best known asymptotic result for ORAM is due to the hierarchical structure of Kushilevitz et al. [6] (O ( log 2N log logN)), tree based ORAM constructions are much simpler.