Multi-Client Oblivious RAM with Poly-Logarithmic Communication

Chow SSM, Fech K, Lai RWF, Malavolta G (2020)

Publication Type: Conference contribution, Original article

Publication year: 2020

Conference Proceedings Title: ASIACRYPT 2020

DOI: 10.1007/978-3-030-64834-3_6

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(√n) communication and client computation for a database of size n. Whether it is possible to reduce these complexities to 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.

Authors with CRIS profile

Katharina Fech Lehrstuhl für Informatik 13 (Angewandte Kryptographie) Wai Fu Lai Lehrstuhl für Informatik 13 (Angewandte Kryptographie)

Involved external institutions

The Chinese University of Hong Kong (CUHK) CN China (CN)

How to cite

APA:

Chow, S.S.M., Fech, K., Lai, R.W.F., & Malavolta, G. (2020). Multi-Client Oblivious RAM with Poly-Logarithmic Communication. In ASIACRYPT 2020.

MLA:

Chow, Sherman S. M., et al. "Multi-Client Oblivious RAM with Poly-Logarithmic Communication." Proceedings of the ASIACRYPT 2020 2020.

BibTeX: Download