Multi-Client Oblivious RAM secure against Malicious Servers

Abstract. It has been an open question whether Oblivious RAM stored on a ma-licious server can be securely shared among multiple clients. The challenge is that ORAMs are stateful, and clients would need to exchange updated state to maintain security. However, clients often do not have a way to directly commu-nicate, and a malicious server can tamper with state information and thus break security. We answer the question of multi-client ORAM on malicious servers af-firmatively by providing several new, efficient multi-client ORAM constructions. We first extend the classical square-root ORAM by Goldreich and the hierarchical one by Goldreich and Ostrovsky to become multi-client secure. We accomplish this by separating the critical parts of the access, which depend on the state of the ORAM, from the non-critical parts (cache access) that can be executed securely in any state. Our second and main contribution is a secure multi-client variant of Path ORAM. To enable secure meta-data update during evictions in Path ORAM, we employ our first result, small multi-client secure classical ORAMs, as a build-ing block. Depending on the block size, the overhead of our multi-client secure construction reaches a low O(logn) communication complexity per client, sim-ilar to state-of-the-art single-client ORAMs.