Paper 2015/121

Multi-Client Oblivious RAM secure against Malicious Servers

Travis Mayberry and Erik-Oliver Blass and Guevara Noubir

Abstract

It has been an open question whether Oblivious RAM stored on a malicious 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 communicate, and a malicious server can tamper with state information and thus break security. We answer the question of multi-client ORAM on malicious servers affirmatively 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 building block. Depending on the block size, the overhead of our multi-client secure construction reaches a low O(log n) communication complexity per client, similar to state-of-the-art single-client ORAMs.