Paper 2020/1551

Multi-Client Oblivious RAM with Poly-Logarithmic Communication

Sherman S. M. Chow, Katharina Fech, Russell W. F. Lai, and Giulio Malavolta


Oblivious RAM enables oblivious access to memory in the single-client setting, which may not be the best fit in the network setting. Multi-client oblivious RAM (MCORAM) considers a collaborative but untrusted environment, where a database owner selectively grants read access and write access to different entries of a confidential database to multiple clients. Their access pattern must remain oblivious not only to the server but also to fellow clients. This upgrade rules out many techniques for constructing ORAM, forcing us to pursue new techniques. MCORAM not only provides an alternative solution to private anonymous data access (Eurocrypt 2019) but also serves as a promising building block for equipping oblivious file systems with access control and extending other advanced cryptosystems to the multi-client setting. Despite being a powerful object, the current state-of-the-art is unsatisfactory: The only existing scheme requires $O(\sqrt n)$ communication and client computation for a database of size $n$. Whether it is possible to reduce these complexities to $\mathsf{polylog}(n)$, thereby matching the upper bounds for ORAM, is an open problem, i.e., can we enjoy access control and client-obliviousness under the same bounds? Our first result answers the above question affirmatively by giving a construction from fully homomorphic encryption (FHE). Our main technical innovation is a new technique for cross-key trial evaluation of ciphertexts. We also consider the same question in the setting with $N$ non-colluding servers, out of which at most $t$ of them can be corrupt. We build multi-server MCORAM from distributed point functions (DPF), and propose new constructions of DPF via a virtualization technique with bootstrapping, assuming the existence of homomorphic secret sharing and pseudorandom generators in NC0, which are not known to imply FHE.

Available format(s)
Publication info
Published by the IACR in ASIACRYPT 2020
multi-client oblivious RAMaccess controlhomomorphic encryptiondistributed point functionhomomorphic secret sharing
Contact author(s)
sherman @ ie cuhk edu hk
fech @ cs fau de
lai @ cs fau de
giulio malavolta @ hotmail it
2020-12-13: received
Short URL
Creative Commons Attribution


      author = {Sherman S.  M.  Chow and Katharina Fech and Russell W.  F.  Lai and Giulio Malavolta},
      title = {Multi-Client Oblivious RAM with Poly-Logarithmic Communication},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1551},
      year = {2020},
      doi = {10.1007/978-3-030-64834-3_6},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.