Improved bounds for Path ORAM

(Elaine Shi)

Path ORAM (Oblivious RAM) is a protocol to hide memory access patterns. A client wants to access memory from an untrusted server; Path ORAM “adds random noise” to the memory accesses so the server learns nothing about which memory was accessed.

A solution to this problem would improve the efficiency of Path ORAM.

We will analyze a random process on the following data structure. In a binary tree of depth $L$, every node has a “bucket” that can store up to $Z$ blocks. (Imagine $Z$ is 3 or 5.) Additionally, the root note has a “stash” which has infinite capacity to store blocks.

You have a total of $N \leq 2^L$ blocks; to start with, none of the blocks are stored in the data structure. After an “initialization” step, you want to perform a sequence of $s$ “read/write” operations. The sequence of read/writes is described as a sequence $a_1, a_2, \ldots, a_s$ of blocks, where $1 \leq a_i \leq N$.

• Initialization: you assign to each block $b$ a “label” $y_b$. The label is one of the $2^L$ leaves of the binary tree; the $N$ labels are assigned independently at random from among the $2^L$ leaves.

  After block $b$ is inserted into the tree, its position in the tree must always be an ancestor of its label $y_b$. (However, the initialization step does not insert any blocks into the tree.)

• Sequentially for each $i$ from $1$ to $s$, apply the following procedure.
  • Let $x = y_{a_i}$ be the label currently assigned to the block $a_i$. In this step, you will only touch buckets along the path from the root to $x$.
  • Assign to block $a_i$ a new label $y_{a_i}$, chosen uniformly at random from among the $2^L$ leaves of the tree.
  • Move block $a_i$ into the “stash” at the root of the tree.
  • Iterate through the blocks in the path from root to leaf $x$. For each such block, move it as far as possible toward the leaf $x$, subject to the following conditions: _ Block $b$ can only be moved to a node that is an ancestor of its label $y_b.$ _ Block $b$ can only be moved to a node that is an ancestor of $x$. * At most $Z$ blocks can be stored in any bucket.

The problem is to prove that not too many blocks end up stored in the stash. Specifically, prove that the probability that the stash ends up holding more than $R$ blocks after $s$ steps is less than $C (1 - \varepsilon)^R$, for some constants $C$ and $\varepsilon > 0$.

For $Z = 5$, the result is known to be true. A proof can be found in Section 5 of this paper. Numerical experiments suggest that it is also true for $Z = 3$. Can you prove it for $3$ or even $4$?