Oblivious RAM (ORAM) allows a client to out-source 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 219, 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.

Oblivious RAM (ORAM) allows a client to outsource database storage to a remote server while hiding the data access pattern. Existing designs use non-linear data structures (e.g., trees or hierarchical structures) and follow a online-offline paradigm. Clients submit their queries in the online phase and then the queries are ''flushed'' in the offline (eviction) phase. Such designs are interactive, requiring more than one round of client-server communication, be it during the online, offline, or both phases. Moreover, the client has to maintain an internal state which depends on the database state.

Machine learning as a service scenario typically requires the client to trust the server and provide sensitive data in plaintext. However, with the recent improvements in fully homomorphic encryption (FHE) schemes, many such applications can be designed in a privacy-preserving way. In this work, we focus on such a problem, private decision tree evaluation (PDTE) --- where a server has a decision tree classification model, and a client wants to use the model to classify her private data without revealing the data or the classification result to the server. We present an efficient non-interactive design of PDTE, that we call SortingHat, based on FHE techniques. As part of our design, we solve multiple cryptographic problems related to FHE: (1) we propose a fast homomorphic comparison function where one input can be in plaintext format; (2) we design an efficient binary decision tree evaluation technique in the FHE setting, which we call homomorphic traversal, and apply it together with our homomorphic comparison to evaluate private decision tree classifiers, obtaining running times orders of magnitude faster than the state of the art; (3) we improve both the communication cost and the time complexity of transciphering, by applying our homomorphic comparison to the FiLIP stream cipher. Through a prototype implementation, we demonstrate that our improved transciphering solution runs around 400 times faster than previous works. We finally present a choice in terms of PDTE design: we present a version of SortingHat without transciphering that achieves significant improvement in terms of computation cost compared to prior works, and another version t-SortingHat with transciphering that has a communication cost about 20 thousand times smaller but comparable running time.