Welcome to the resource topic for 2015/121
Title:
Multi-Client Oblivious RAM secure against Malicious Servers
Authors: Travis Mayberry, Erik-Oliver Blass, Guevara Noubir
Abstract: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.
ePrint: https://eprint.iacr.org/2015/121
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .