OBI: a multi-path oblivious RAM for forward-and-backward-secure searchable encryption

—Dynamic searchable encryption (DSE) is a user-cloud protocol for searching over outsourced encrypted data. Many current DSE schemes resort to oblivious RAMs (ORAM) to achieve forward privacy and backward privacy, which is a concept to describe security levels of the protocol. We show that, however, most prior ORAM-based DSE suffers from a new problem: it is inefficient to fetch/insert a large set of data blocks. We call this the large-stash eviction problem. To address the problem, we present OBI, a multi-path Oblivious RAM, which accesses multiple tree paths per query for handling a large set of data blocks. We classify traditional tree-based ORAMs as single-path ORAMs if they access a single path per query. OBI has two new high-throughput multi-path eviction algorithms that are several orders of magnitude more efficient than the well-known PATH-ORAM eviction algorithm when the stash is large. We prove that the proposed multi-path ORAM outperforms the traditional single-path ORAM in terms of local stash size and insertion efficiency. Security analysis shows that OBI is secure under the strong forward and backward security model. OBI can protect the well-known DSE leakage, such as the search pattern and the size pattern. We also show that OBI can be applied to oblivious file systems and oblivious conjunctive-query DSE schemes. We conduct experiments on the Enron dataset. The experimental results demonstrate that OBI is far more efficient than the state-of-the-art ORAM-based DSE schemes.