Technical Report MSC-2018-30

Title: New Efficient Constructions for Distributed Oblivious RAM
Authors: Tamer Mour
Supervisors: Eyal Kushilevitz
PDFCurrently accessibly only within the Technion network
Abstract: As resource-limited individuals and organizations increasingly rely on third-party cloud services to store and compute on sensitive data online, the necessity for privacy-preserving storage mechanisms arises.

Generally, we can envision a client with small local storage, who outsources his large private data to a remote untrusted server. The client accesses blocks in the data by performing read/write queries to the server. Besides keeping the data private, a task which can be achieved by symmetric encryption, the client may wish to hide the access pattern to the data (i.e. which blocks are accessed), since in many scenarios such a pattern is sensitive information by itself, or it can possibly leak information about the data. For instance, in the scenario where a client performs queries to a database of stock quotes, the access pattern might reveal information about the trading habits of the client.

We capture the client-server interaction described above using the RAM model, where the client acts as a CPU, which interacts with the server in order to execute RAM programs over the data in the memory. Oblivious RAM (ORAM) is a cryptographic primitive that allows a client in such a setting to simulate an execution of a RAM program while hiding the access pattern from the server. Distributed ORAM is a variant of ORAM, where the data is stored in $m$ non-colluding servers, with which the client interacts simultaneously.

Naturally, an ORAM simulation of a program may cause a blow-up in various measures, relatively to a regular execution, such as the server storage size, the local computation complexity, and most importantly, the amount of queries made to the server, which is referred to as the bandwidth overhead of an ORAM scheme. Extensive research over the last few decades have succeeded to reduce the overhead of ORAMs, both in the single-server and the multi-server setting, from $O(\sqrt{N})$ to $O(1)$. However, all known protocols that achieve a sub-logarithmic blow-up either require heavy server-side computation (e.g. homomorphic encryption), or a large block size of at least $\Omega(\log^3 N)$.

In this work, we present a family of distributed ORAM constructions that follow the hierarchical approach of Goldreich and Ostrovsky [GO96] in the single server setting. We enhance known techniques, and develop new ones, to take better advantage of the existence of multiple servers. By plugging known hashing schemes in our constructions, we get the following results:

1. For any number $m\geq 2$ of servers, we show an $m$-server ORAM scheme with $O(\log N/\log\log N)$ overhead, and block size $\Omega(\log^2 N)$. This scheme is private even against a collusion of up to $m-1$ servers. 2. A three-server ORAM construction with $O(\omega(1)\log N/\log\log N)$ overhead and a block size almost logarithmic, i.e. $\Omega(\log^{1+\epsilon}N)$. \end{enumerate}

We also investigate a model where the servers are allowed to perform a linear amount of light local computations, and show that constant overhead is achievable in this model, through a simple four-server ORAM protocol. Through the theoretical lens, this is the first ORAM scheme with asymptotic constant overhead, and polylogarithmic block size, that does not use homomorphic encryption. Practically speaking, although we do not provide an implementation of the suggested construction, evidence from related work (e.g.[DS17]) makes us believe that despite the linear computational overhead, the construction can be potentially very efficient practically, in particular when applied to secure computation.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2018
To the main CS technical reports page

Computer science department, Technion