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.
Category / Keywords: cryptographic protocols / Multi-client ORAM, malicious security Original Publication (with major differences): ACNS 2017 Date: received 13 Apr 2017 Contact author: reinert at cs uni-saarland de Available format(s): PDF | BibTeX Citation Version: 20190305:125121 (All versions of this report) Short URL: ia.cr/2017/329