Date de l'exposé : 02 juin 2023
Panacea: Non-interactive and Stateless Oblivious RAM
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.
