Paper 2023/274

Panacea: Non-interactive and Stateless Oblivious RAM

Kelong Cong, Zama
Debajyoti Das, KU Leuven
Georgio Nicolas, KU Leuven
Jeongeun Park, Norwegian University of Science and Technology

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, at the cost of a computationally expensive client-side offline phase. Furthermore, such a scheme can be categorized as a stateful construction, meaning that the client has to locally maintain a dynamic state representing the order of remote database elements. We present Panacea: a novel design of ORAM based on FHE techniques, which 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 delegates all expensive computation 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, but less amortized bandwidth. Our experimental results show that our design, with the 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 the statelessness and low computational overhead on the client, and reasonable computational overhead on the server, our design is very suitable to be deployed as a cloud-based privacy-preserving storage outsourcing solution with a portable client running on a lightweight device.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Euro S&P 2024
Contact author(s)
kelong cong @ zama ai
debajyoti das @ esat kuleuven be
georgio nicolas @ esat kuleuven be
jeongeun park @ ntnu no
2024-04-16: last of 5 revisions
2023-02-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Kelong Cong and Debajyoti Das and Georgio Nicolas and Jeongeun Park},
      title = {Panacea: Non-interactive and Stateless Oblivious {RAM}},
      howpublished = {Cryptology ePrint Archive, Paper 2023/274},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.