Cryptology ePrint Archive: Report 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.

Category / Keywords: multi-client oblivious RAM, access control, homomorphic encryption, distributed point function, homomorphic secret sharing

Original Publication (in the same form): IACR-ASIACRYPT-2020

Date: received 11 Dec 2020

Contact author: sherman at ie cuhk edu hk,fech@cs fau de,lai@cs fau de,giulio malavolta@hotmail it

Available format(s): PDF | BibTeX Citation

Version: 20201213:170652 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]