International Association
for Cryptologic Research

Outsourcing data to remote storage servers has become more and more popular, but the related security and privacy concerns have also been raised. To protect the pattern in which a user accesses the outsourced data, various oblivious RAM (ORAM) constructions have been designed. However, when existing ORAM designs are extended to support multi-user scenarios, they become vulnerable to stealthy privacy attacks targeted at revealing the data access patterns of innocent users, even if only one curious or compromised user colludes with the storage server. To study the feasibility and costs of overcoming the above limitation, this paper proposes a new ORAM construction called Multi-User ORAM (MU-ORAM), which is resilient to stealthy privacy attacks. The key ideas in the design are (i) introduce a chain of proxies to act as a common interface between users and the storage server, (ii) distribute the shares of the system secrets delicately to the proxies and users, and (iii) enable a user and/or the proxies to collaboratively query and shuffle data. Through extensive security analysis, we quantify the strength of MU-ORAM in protecting the data access patterns of innocent users from attacks, under the assumption that the server, users, and some but not all proxies can be curious but honest, compromised and colluding. Cost analysis has been conducted to quantify the extra overhead incurred by the MU-ORAM design.