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

Abstract

Dynamic searchable encryption (DSE) is a usercloud 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 singlepath 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 wellknown 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.

Topics & Concepts