# Oblivious RAM Done Right(5): Lower Bound

Written by Chenyang Yu, for CS 282B final presentation.

1. Simons Institute Talk: “Oblivious RAM” by Boyle
2. Software protection and simulation on oblivious RAMs” by Goldreich and Ostrovsky, we will refer it as [GO96]
3. Is There an Oblivious RAM Lower Bound?” by Boyle and Naor
4. Simons Institute Talk: “Yes, There is an Oblivious RAM Lower Bound!” by Larsen
5. Yes, There is an Oblivious RAM Lower Bound!” by Larsen and Nielsen

In particular, number 5 is the paper that I am presenting (picked from CRYPTO 2018).

## Terminology:

Online: The content of the operation sequence is given to the ORAM one at a time.

Offline: The ORAM is given the entire operation sequence ahead of simulation time.

Bandwidth overhead: The multiplicative factor extra memory blocks that must be accessed to hide the operation sequence. The formula will be given later. When we say “upper bound” or “lower bound” of ORAM, we always mean the bound of amortized bandwidth overhead.

Balls in bins: The data items are modeled as “balls”, and CPU registers and server-side memory are modeled as “bins”, and the set of allowed data operations consists only of moving balls between bins, in other word, shuffling.

Active: Allow the server to perform untrusted computation on behalf of the user.

Passive: Doesn’t allow the server to perform untrusted computation on behalf of the user.

## Overview:

ORAM was first introduced for hiding memory access pattern in a software protection context. The main performance metric of an ORAM is the bandwidth overhead. In lectures, we studied square root solutions, hierarchy solution, and so on, in great details. Those models were built for pushing down the upper bound. Today, we are going to discuss the lower bound. In [GO96], we already had a $\Omega(log n)$ lower bound. Is there anything we can do to further reduce the lower bound?

## Directions:

There are three directions to think about for further exploring lower bound:

1. [GO96] lower bound only applies to “balls in bins” algorithms, so we may consider to remove this assumption. Boyle and Naor removed this assumption and showed it will result in super linear lower bounds for sorting circuits. To overcome this barrier, they proposed an “online” ORAM. They also argued that most implementations of ORAM fall into the “online” category.
2. [GO96] lower bound holds even for offline ORAM. Boyle and Naor pointed out that most practical constructions of ORAM are online, so we may hope to find a better lower bound for online ORAM only.
3. [GO96] lower bound crucially relies on the statistically closeness of access pattern distributions for any two inputs. In many cases, statistical security might be stronger than necessary, so we may consider to relax this assumption to computationally secure, which is sufficient in real world application. Note that in [GO96], authors pointed out that in practice, one can implement such ORAM using PRFs, so the result is computationally secure only. But the lower bound was proved assuming access to random oracle, so that the proof itself relies on statistical closeness. Hence by “relaxing this assumption”, I mean for proving lower bound, not for implementation.

All together, in this paper, we are going to prove a lower bound for non-“balls in bins” ORAM that is online, passive and computationally secure only. That is, the ORAM algorithm can be arbitrary, the adversary must be efficient, and it holds only for online ORAM.

## Definitions and Notations:

An online ORAM supports the following two operations:

1. $write(a, data)$: Store data in the block of address a, where $a \in [n]$ and $data \in \{0.1\}^{r}$.
2. $read(a)$: Return the contents of the block of address a.

We refer to blocks at the server as “memory cells“, where each cell contains w bits. We refer to blocks in the ORAM array as “entries“, where each block contains r bits. Note that this “r” is just the length of “data” as defined above. We also let the client memory to have m bits. Note that if after N accesses the ORAM makes M probes, then the bandwidth overhead is $Mw/Nr$.

Let y be an operation sequence: $y := (op_{1}, ... , op_{M})$, where $op_{i} \in \{write, read\}$. Let $A(y) := (A(op_{1}), A(op_{2}), ... , A(op_{M}))$ denote the memory access pattern to the server from the online ORAM, where each $A(op_{i})$ represents the list of addresses of the memory cells accessed at the server while processing operation $op_{i}$.

An online ORAM is secure in the following sense: for two distinct operation sequences y and z with length M, A(y) and A(z) are computationally indistinguishable.

## Main Theorem (informal):

Theorem: In such setting, any online ORAM must have an expected amortized bandwidth overhead of $\Omega(log(nr/m))$ on sequences of $\Theta(n)$ operations.

Comment: Note that this theorem holds in the random oracle model, requiring only computational indistinguishability, holds for any $w$ and allows for arbitrary representations of the data in memory. For the natural setting of parameters $r \leq m \leq n^{1-\epsilon}$ for arbitrary small constant $\epsilon > 0$, the lower bound simplifies to $\Omega(log n)$.

## Proof Strategy:

Note that above definition is very close to the definition of an oblivious data structure, which is defined as follows:

Definition: In the array maintenance problem, we must maintain any array $B$ of $n$ $r$-bit entries under the following two operations:

1. $write(a, data)$: Set the contents of B[a] to data, where $a \in [n]$ and $data \in \{0,1\}^{r}$.
2. $read(a)$: Return the contents of B[a].

Hence the idea is to prove a lower bound for oblivious data structures solving the array maintenance problem, and then use the same technique to prove the same lower bound for online ORAM.

## Models:

Data Structure lower bounds are typically proved in the cell probe model of Yao. The model is very similar to standard RAM, the difference is that the computation is free and we only pay for memory accesses. To meet our goal, we will define our model as “oblivious cell probe model“. Based on this model, we will use “information transfer” method. This method comes from the paper “Logarithmic Lower Bounds in the Cell-Probe Model“.

The first page of the handout contains a graph of such model. Each operation can be a read or a write. Each operation $op$ makes read and write probes to the server memory. The sequence of probes made during an operation $op$ is called the access pattern of $op$ and is written as $A(op)$. Words in the server memory are called cells. Each cell is $w$ bits. The ORAM is restricted to $m$ bits of storage between two operations. During an operation it can use unlimited storage.