eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2017/329

Maliciously Secure Multi-Client ORAM

Matteo Maffei, Giulio Malavolta, Manuel Reinert, and Dominique Schröder


Oblivious RAM (ORAM) has emerged as an enabling technology to secure cloud-based storage services. The goal of this cryptographic primitive is to conceal not only the data but also the access patterns from the server. While the early constructions focused on a single client scenario, a few recent works have focused on a setting where multiple clients may access the same data, which is crucial to support data sharing applications. All these works, however, either do not consider malicious clients or they significantly constrain the definition of obliviousness and the system's practicality. It is thus an open question whether a natural definition of obliviousness can be enforced in a malicious multi-client setting and, if so, what the communication and computational lower bounds are. In this work, we formalize the notion of maliciously secure multi-client ORAM, we prove that the server-side computational complexity of any secure realization has to be $\Omega(n)$, and we present a cryptographic instantiation of this primitive based on private information retrieval techniques, which achieves an $O(\sqrt{N})$ communication complexity. We further devise an efficient access control mechanism, built upon a novel and generally applicable realization of plaintext equivalence proofs for ciphertext vectors. Finally, we demonstrate how our lower bound can be bypassed by leveraging a trusted proxy, obtaining logarithmic communication and server-side computational complexity. We implemented our scheme and conducted an experimental evaluation, demonstrating the feasibility of our approach.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. ACNS 2017
Multi-client ORAMmalicious security
Contact author(s)
reinert @ cs uni-saarland de
2017-04-17: received
Short URL
Creative Commons Attribution


      author = {Matteo Maffei and Giulio Malavolta and Manuel Reinert and Dominique Schröder},
      title = {Maliciously Secure Multi-Client ORAM},
      howpublished = {Cryptology ePrint Archive, Paper 2017/329},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/329}},
      url = {https://eprint.iacr.org/2017/329}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.