Memory organization of the oblivious program

The program Π′ stores a complete binary tree T of depth ${\displaystyle d=\log(n/\alpha )}$ in its memory. Each node in T is represented by a binary string of length at most d. The root is the empty string, denoted by λ. The left and right children of a node represented by the string ${\displaystyle \gamma }$ are ${\displaystyle \gamma _{0}}$ and ${\displaystyle \gamma _{1}}$ respectively. The program Π′ thinks of the memory of Π as being partitioned into blocks, where each block is a contiguous sequence of memory cells of size α. Thus, there are at most ${\displaystyle \lceil n/\alpha \rceil }$ blocks in total. In other words, the memory cell r corresponds to block ${\displaystyle b=\lfloor r/\alpha \rfloor }$.

An illustration of the memory of the oblivious program showing the binary tree and position map.

At any point in time, there is an association between the blocks and the leaves in T. To keep track of this association, Π′ also stores a data structure called a position map, denoted by ${\displaystyle Pos}$, using ${\displaystyle O(n/\alpha )}$ registers. This data structure, for each block b, stores the leaf of T associated with b in ${\displaystyle Pos(b)}$.

Each node in T contains an array with at most K triples. Each triple is of the form ${\displaystyle (b,Pos(b),v)}$, where b is a block identifier and v is the contents of the block. Here, K is a security parameter and is ${\displaystyle O({\text{poly}}\log n)}$.

Description of the oblivious program

The program Π′ starts by initializing its memory as well as registers to ⊥. Describing the procedures, Owrite and Oread is enough to complete the description of Π′. The sub-routine Owrite is given below. The inputs to the sub-routine are a memory location ${\displaystyle l\in [n]}$ and the value v to be stored at the location l. It has three main phases, namely FETCH, PUT_BACK, and FLUSH.

 input: a location l, a value v

 Procedure FETCH  // Search for the required block.
   ${\displaystyle b\leftarrow \lfloor l/\alpha \rfloor }$    // b is the block containing l.
   ${\displaystyle i\leftarrow l\mod \alpha }$    // i is l's component in block b.
   ${\displaystyle pos\leftarrow Pos(b)}$
   if ${\displaystyle pos=\perp }$ then ${\displaystyle pos\leftarrow _{R}[n/\alpha ]}$.    // Set pos to a uniformly random leaf in T.
   flag ${\displaystyle \leftarrow 0}$.
   for each node N on the path from the root to pos do
     if N has a triple of the form ${\displaystyle (b,pos,x)}$ then
       Remove ${\displaystyle (b,pos,x)}$ from N, store x in a register, and write back the updated N to T.
       flag ${\displaystyle \leftarrow 1}$.
     else
       Write back N to T.

 Procedure PUT_BACK  // Add back the updated block at the root.
   ${\displaystyle pos'\leftarrow _{R}[n/\alpha ]}$.  // Set pos' to a uniformly random leaf in T.
   if flag${\displaystyle =1}$ then
     Set x' to be the same as x except for v at the i-th position.
   else
     Set x' to be a block with v at i-th position and ⊥'s everywhere else.
   if there is space left in the root then
     Add the triple ${\displaystyle (b,pos',x')}$ to the root of T.
   else
     Abort outputting overflow.

 Procedure FLUSH  // Push the blocks present in a random path as far down as possible.
   ${\displaystyle pos^{*}\leftarrow _{R}[n/\alpha ]}$.  // Set ${\displaystyle pos^{*}}$ to a uniformly random leaf in T.
   for each triple ${\displaystyle (b'',pos'',v'')}$ in the nodes traversed the path from the root to ${\displaystyle pos^{*}}$
     Push down this triple to the node N that corresponds to the longest common prefix of ${\displaystyle pos''}$ and ${\displaystyle pos^{*}}$.
     if at any point some bucket is about to overflow then
       Abort outputting overflow.

The task of the FETCH phase is to look for the location l in the tree T. Suppose pos is the leaf associated with the block containing location l. For each node N in T on the path from root to pos, this procedure goes over all triples in N and looks for the triple corresponding to the block containing l. If it finds that triple in N, it removes the triple from N and writes back the updated state of N. Otherwise, it simply writes back the whole node N.

In the next phase, it updates the block containing l with the new value v, associates that block with a freshly sampled uniformly random leaf of the tree, and writes back the updated triple to the root of T.

The last phase, which is called FLUSH, is an additional operation to release the memory cells in the root and other higher internal nodes. Specifically, the algorithm chooses a uniformly random leaf ${\displaystyle pos^{*}}$ and then tries to push down every node as much as possible along the path from root to ${\displaystyle pos^{*}}$. It aborts outputting an overflow if at any point some bucket is about to overflow its capacity.

The sub-routine Oread is similar to Owrite. For the Oread sub-routine, the input is just a memory location ${\displaystyle l\in [n]}$ and it is almost the same as Owrite. In the FETCH stage, if it does not find a triple corresponding to location l, it returns ⊥ as the value at location l. In the PUT_BACK phase, it will write back the same block that it read to the root, after associating it with a freshly sampled uniformly random leaf.

Correctness of the simple ORAM scheme

Let C stand for the ORAM compiler that was described above. Given a program Π, let Π′ denote ${\displaystyle C(\Pi )}$. Let ${\displaystyle \Pi (n,x)}$ denote the execution of the program Π on an input x using n memory cells. Also, let ${\displaystyle {\tilde {\Pi }}(n,x)}$ denote the memory access pattern of ${\displaystyle \Pi (n,x)}$. Let μ denote a function such that for any ${\displaystyle n\in \mathbb {N} }$, for any program Π and for any input ${\displaystyle x\in \{0,1\}^{*}}$, the probability that ${\displaystyle \Pi '(n,x)}$ outputs an overflow is at most ${\displaystyle \mu (n)}$. The following lemma is easy to see from the description of C.

Equivalence Lemma

Let ${\displaystyle n\in \mathbb {N} }$ and ${\displaystyle x\in \{0,1\}^{*}}$. Given a program Π, with probability at least ${\displaystyle 1-\mu (n)}$, the output of ${\displaystyle \Pi '(n,x)}$ is identical to the output of ${\displaystyle \Pi (n,x)}$.

It is easy to see that each Owrite and Oread operation traverses root-to-leaf paths in T chosen uniformly and independently at random. This fact implies that the distribution of memory access patterns of any two programs that make the same number of memory accesses are indistinguishable if they both do not overflow.

Obliviousness Lemma

Given two programs ${\displaystyle \Pi _{1}}$ and ${\displaystyle \Pi _{2}}$ and two inputs ${\displaystyle x_{1},x_{2}\in \{0,1\}^{*}}$ such that ${\displaystyle |{\tilde {\Pi _{1}}}(x_{1},n)|=|{\tilde {\Pi _{2}}}(x_{2},n)|}$, with probability at least ${\displaystyle 1-2\mu (n)}$, the access patterns ${\displaystyle {\tilde {\Pi _{1}'}}(x_{1},n)}$ and ${\displaystyle {\tilde {\Pi _{2}'}}(x_{2},n)}$ are identical.

The following lemma completes the proof of correctness of the ORAM scheme.

Overflow Lemma

There exists a negligible function μ such that for every program Π, every n and input x, the program ${\displaystyle \Pi '(n,x)}$ outputs overflow with probability at most ${\displaystyle \mu (n)}$.

Computational and memory overheads

During each Oread and Owrite operation, two random root-to-leaf paths of T are fully explored by Π′. This takes ${\displaystyle O(K\cdot \log(n/\alpha ))}$ time. This is the same as the computational overhead and is ${\displaystyle O({\text{poly}}\log n)}$ since K is ${\displaystyle O({\text{poly}}\log n)}$.

The total memory used up by Π′ is equal to the size of T. Each triple stored in the tree has ${\displaystyle \alpha +2}$ words in it and thus there are ${\displaystyle K(\alpha +2)}$ words per node of the tree. Since the total number of nodes in the tree is ${\displaystyle O(n/\alpha )}$, the total memory size is ${\displaystyle O(nK)}$ words, which is ${\displaystyle O(n{\text{ poly}}\log n)}$. Hence, the memory overhead of the construction is ${\displaystyle O({\text{poly}}\log n)}$.