You are looking at a specific version 20201213:170652 of this paper. See the latest version.

Paper 2020/1551

Multi-Client Oblivious RAM with Poly-Logarithmic Communication

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

Abstract

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.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in ASIACRYPT 2020
DOI
10.1007/978-3-030-64834-3_6
Keywords
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
History
2020-12-13: received
Short URL
https://ia.cr/2020/1551
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.