[Resource Topic] 2023/274: Panacea: Non-interactive and Stateless Oblivious RAM

Welcome to the resource topic for 2023/274

Panacea: Non-interactive and Stateless Oblivious RAM

Authors: Kelong Cong, Debajyoti Das, Georgio Nicolas, Jeongeun Park


Oblivious RAM (ORAM) allows a client to outsource storage to a remote server while hiding the data access pattern from the server. Many ORAM designs have been proposed to reduce the computational overhead and bandwidth blowup for the client. A recent work, Onion Ring ORAM (CCS’19), is able to achieve O(1) bandwidth blowup in the online phase using fully homomorphic encryption (FHE) techniques. However, it requires a computationally expensive client-side offline phase to do so. Furthermore, it is a stateful construction, which means that the client has to maintain a state of the database locally. We present Panacea: a novel design of ORAM based on FHE techniques, that is non-interactive and stateless, achieves O(1) bandwidth blowup, and does not require an expensive offline phase for the client to perform; in that sense, our design is the first of its kind among other ORAM designs. To provide the client with such performance benefits, our design pushes all of expensive computations to the resourceful server. We additionally show how to boost the server performance significantly using probabilistic batch codes at the cost of only 1.5x in additional bandwidth blowup and 3x expansion in server storage. Our experimental results show that our design, with the employment of this batching technique, is practical in terms of server computation overhead as well. Specifically, for a database size of 2^{19}, it takes only 1.16 seconds of amortized computation time for a server to respond to a query. As a result of our client’s statelessness, low computational overhead and practical computational overhead with the server, our design is ideal to be deployed as a cloud-based privacy-preserving storage outsourcing solution.

ePrint: https://eprint.iacr.org/2023/274

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 .