Paper 2015/121

Multi-Client Oblivious RAM secure against Malicious Servers

Travis Mayberry, Erik-Oliver Blass, and Guevara Noubir


This paper tackles the open problem whether an Oblivious RAM can be shared among multiple clients in the presence of a fully malicious server. Current ORAM constructions rely on clients knowing the ORAM state to not reveal information about their access patter. With multiple clients, a straightforward approach requires clients exchanging updated state to maintain security. However, clients on the internet usually cannot directly communicate with each other due to NAT and firewall settings. Storing state on the server is the only option, but a malicious server can arbitrarily tamper with that information. We first extend the classical square-root ORAM by Goldreich and the hierarchical one by Goldreich and Ostrovsky to add muti-client security. We accomplish this by separating the critical portions 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 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 communication complexity 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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
oblivious ram
Contact author(s)
mayberry @ usna edu
2017-07-17: last of 6 revisions
2015-02-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Travis Mayberry and Erik-Oliver Blass and Guevara Noubir},
      title = {Multi-Client Oblivious RAM secure against Malicious Servers},
      howpublished = {Cryptology ePrint Archive, Paper 2015/121},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.