Oblivious RAM

An oblivious RAM (ORAM) is a client algorithm that serves reads and writes to a virtual array of $N_1$ blocks by issuing reads and writes to a physical array of $N_2$ blocks held by a server, so that the sequence of physical addresses it touches reveals nothing about the virtual operations. It was introduced by Gol87 and Ost90, whose results GO96 unify and extend.

Note: Oblivious RAM schemes can provide statistical or unconditional security against adversaries who only know which array indices are accessed. However, in practice one almost always needs to deploy ORAM together with standard symmetric encryption.

Syntax

Throughout, we use the following notation. All oblivious RAM schemes are defined with respect to a key space $\mathsf{KSp}$, state space $\mathsf{StSp}$, virtual array size $N_1$ and blocks ${\mathcal{B}}_1$, and physical array size $N_2$ and blocks ${\mathcal{B}}_2$. We additionally assume $\perp \in \mathsf{StSp}$ and $\perp \notin {\mathcal{B}}_1$, and write ${\beta }_j:=\lceil {\log }_2|{\mathcal{B}}_j|\rceil$ for the block length in bits. Furthermore, we define the sets:

• ${\mathsf{RdOps}}_j=\{1,\dots ,N_j\}$
• ${\mathsf{WrOps}}_j=\{(i,b)\mid i\in {\mathsf{RdOps}}_j,b\in {\mathcal{B}}_j\}$
• ${\mathsf{Ops}}_j={\mathsf{RdOps}}_j\cup {\mathsf{WrOps}}_j$

These are the allowed operations for the virtual array ($j=1$) and the physical array ($j=2$). An $r$-round Oblivious RAM (ORAM) is a tuple of efficient functions $(\mathsf{Gen},{\mathsf{Acc}}_1,\dots ,{\mathsf{Acc}}_r,\mathsf{Out})$ such that:

• $\mathsf{Gen}(1^{\lambda })\to K$, a randomized function outputting a key $K\in \mathsf{KSp}$.
• ${\mathsf{Acc}}_j(K,\mathsf{st},o,a_1,\dots ,a_{j-1})\to ({\mathsf{st}}^{\prime },p_j)$ for $j\in [r]$, a randomized function taking a state $\mathsf{st}\in \mathsf{StSp}$, a virtual operation $o\in {\mathsf{Ops}}_1$ and the answers $a_1,\dots ,a_{j-1}\in {\mathcal{B}}_2^{\ast }$ of the earlier rounds, and outputting a new state ${\mathsf{st}}^{\prime }\in \mathsf{StSp}$ and a finite sequence $p_j\in {\mathsf{Ops}}_2^{\ast }$ of physical operations.
• $\mathsf{Out}(K,\mathsf{st},o,a_1,\dots ,a_r)\to ({\mathsf{st}}^{\prime },y)$, a function outputting a new state ${\mathsf{st}}^{\prime }\in \mathsf{StSp}$ and an answer $y\in {\mathcal{B}}_1\cup \{\perp \}$.

The above functions describe the processing of the Oblivious RAM query. They are used in the following way to process a virtual operation $o\in {\mathsf{Ops}}_1$, for a physical array $M_2\in {\mathcal{B}}_2^{N_2}$. For $j=1,\dots ,r$, run $(\mathsf{st},p_j)\leftarrow {\mathsf{Acc}}_j(K,\mathsf{st},o,a_1,\dots ,a_{j-1})$ and execute the operations of $p_j$ on $M_2$ in order: a read $i$ returns $M_2[i]$, and a write $(i,b)$ sets $M_2[i]\leftarrow b$. Let $a_j\in {\mathcal{B}}_2^{\ast }$ be the values the reads of $p_j$ return. Finally, run $(\mathsf{st},y)\leftarrow \mathsf{Out}(K,\mathsf{st},o,a_1,\dots ,a_r)$ and return $y$. The client starts from $\mathsf{st}=\perp$ and $M_2=(b_0,\dots ,b_0)$ for a fixed $b_0\in {\mathcal{B}}_2$.

The access pattern of $o$ is $\mathrm{ap}(o):=(\rho (p_1),\dots ,\rho (p_r))$, where $\rho$ maps each read $i$ to $(\mathrm{rd},i)$ and each write $(i,b)$ to $(\mathrm{wr},i)$: it records the index and type of every physical operation, not its contents.

Properties

Correctness

Fix $\lambda$ and a sequence $o_1,\dots ,o_q\in {\mathsf{Ops}}_1$, processed in order from the initial state under $K\leftarrow \mathsf{Gen}(1^{\lambda })$ with answers $y_1,\dots ,y_q$. The correct answer $v_t$ to $o_t$ is $\perp$ when $o_t$ is a write; when $o_t$ is a read $i$, it is the block $b$ of the last write $(i,b)$ among $o_1,\dots ,o_{t-1}$, and $\perp$ if there is none. An ORAM $\Pi =(\mathsf{Gen},{\mathsf{Acc}}_1,\dots ,{\mathsf{Acc}}_r,\mathsf{Out})$ is $(1-\epsilon )$-correct if for all $\lambda ,q\in \mathbb{N}$ and $o_1,\dots ,o_q\in {\mathsf{Ops}}_1$,

$$\mathrm{Pr}\left[\forall t\in [q]:y_t=v_t\right]\ge 1-\epsilon (\lambda ,q),$$

over the coins of $\mathsf{Gen}$, ${\mathsf{Acc}}_1,\dots ,{\mathsf{Acc}}_r$ and $\mathsf{Out}$. It is $(1-\mathrm{negl}(\lambda ))$-correct if $\epsilon (\lambda ,q(\lambda ))$ is negligible for every polynomial $q$. When $\epsilon =0$, we say $\Pi$ is perfectly correct.

Security

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{oram}}_{\Pi,\calA}(\secpar)$}
\begin{algorithmic}
\State $K \gets \Gen(1^\secpar)$; $\st \gets \bot$; $M_2 \gets (b_0, \ldots, b_0)$
\State $b \getsr \bits$
\State $b' \gets \calA^{\calO_b}(1^\secpar)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\algname{Oracle}
\caption{$\calO_b(o_0, o_1)$}
\begin{algorithmic}
\State process $o_b \in \Ops_1$ under $K$, updating $\st$ and $M_2$
\Comment{the answer $y$ is withheld: it differs between the worlds}
\Return $\mathrm{ap}(o_b)$
\end{algorithmic}
\end{algorithm}

The adversary chooses the two operation sequences adaptively, one pair of operations at a time, and sees the access pattern of each operation of the sequence $b$ selects. An ORAM $\Pi$ is secure if it is $(1-\mathrm{negl}(\lambda ))$-correct and for all efficient $\mathcal{A}$,

$${\mathbf{Adv}}_{\Pi ,\mathcal{A}}^{\mathrm{oram}}(\lambda ):=\left|2\mathrm{Pr}\left[{\mathbf{G}}_{\Pi ,\mathcal{A}}^{\mathrm{oram}}(\lambda )=1\right]-1\right|$$

is negligible.

With $N_2=N_1$ and ${\mathcal{B}}_2={\mathcal{B}}_1\cup \{b_0\}$, the linear scan, which on every operation reads all $N_1$ cells in a first round and rewrites all of them in a second, is a perfectly correct and perfectly secure two-round ORAM with bandwidth blowup $2N_1{\beta }_2/{\beta }_1$ — folklore. A client that keeps all $N_1$ blocks in $\mathsf{st}$ and issues no physical operations is perfectly secure too — folklore.

Efficiency

For a sequence $o_1,\dots ,o_q$, let $p_{t,j}$ be the physical operations issued in round $j$ of $o_t$.

• The bandwidth blowup on $o_1,\dots ,o_q$ is $\frac{{\beta }_2}{q{\beta }_1}\cdot \mathbb{E}\left[{\sum }_{t=1}^q{\sum }_{j=1}^r|p_{t,j}|\right]$, and the amortized bandwidth blowup is its maximum over all sequences of $q$ operations with $N_1\le q\le \mathrm{poly}(\lambda )$. The worst-case bandwidth blowup is the maximum of $\frac{{\beta }_2}{{\beta }_1}{\sum }_{j=1}^r|p_{t,j}|$ over all sequences, all $t$ and all coins.
• The client storage is ${\max }_t|{\mathsf{st}}_t|$, the largest state kept between operations, in bits or in blocks of ${\beta }_1$ bits; the key length $|K|$ is reported separately. Answers held within one operation are not counted, since the bandwidth bounds them.
• A client has $O(1)$ blocks of memory at every step, within an operation as well as between operations, as a RAM with a constant number of registers does, if each round issues $O(1)$ physical operations, ${\mathsf{Acc}}_j$ uses $a_1,\dots ,a_{j-1}$ only through $a_{j-1}$ and $\mathsf{st}$, $\mathsf{Out}$ uses them only through $a_r$ and $\mathsf{st}$, and $\mathsf{st}$ has $O(1)$ blocks throughout; the number of rounds $r$ may then grow with $N_1$.
• The server storage is $N_2{\beta }_2$ bits, and the round complexity is $r$.

Variations

Statistically secure ORAM

An ORAM $\Pi$ is statistically secure if it is $(1-\mathrm{negl}(\lambda ))$-correct and ${\mathbf{Adv}}_{\Pi ,\mathcal{A}}^{\mathrm{oram}}(\lambda )$ is negligible for every adversary $\mathcal{A}$, possibly computationally unbounded, that makes polynomially many oracle queries. It is perfectly secure if in addition ${\mathbf{Adv}}_{\Pi ,\mathcal{A}}^{\mathrm{oram}}(\lambda )=0$ for every such $\mathcal{A}$.

Offline ORAM

An offline ORAM learns the indices and types of the whole operation sequence $\mathbf{o}=(o_1,\dots ,o_q)$ before processing starts, but each written block only with its operation: ${\mathsf{Acc}}_j$ and $\mathsf{Out}$ take the current operation $o_t$ together with $(\rho (o_1),\dots ,\rho (o_q))$ in place of $o$, with $\rho$ as in the definition of the access pattern. Knowing the written blocks in advance would let the client answer every read from them without touching the server. In the security game the adversary submits one pair of sequences of equal length and receives the access pattern of the whole execution on one of them. BN16’s offline ORAMs also know the written blocks in advance (offline ORAM with fixed instructions) — BN16. The ORAMs defined above, which process each operation before receiving the next, are online — BN16.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{oram\text{-}off}}_{\Pi,\calA}(\secpar)$}
\begin{algorithmic}
\State $K \gets \Gen(1^\secpar)$; $b \getsr \bits$
\State $(\mathbf{o}_0, \mathbf{o}_1, \stA) \gets \calA(1^\secpar)$
\Comment{$\mathbf{o}_0, \mathbf{o}_1 \in \Ops_1^q$ for the same $q$}
\State process $\mathbf{o}_b$ under $K$ from $\st = \bot$ and $M_2 = (b_0, \ldots, b_0)$
\State $\mathit{ap} \gets (\mathrm{ap}(o_1), \ldots, \mathrm{ap}(o_q))$ for the operations of $\mathbf{o}_b$
\State $b' \gets \calA(\stA, \mathit{ap})$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

An offline ORAM $\Pi$ is secure if it is $(1-\mathrm{negl}(\lambda ))$-correct and for all efficient $\mathcal{A}$,

$${\mathbf{Adv}}_{\Pi ,\mathcal{A}}^{\mathrm{oram}\text{-}\mathrm{off}}(\lambda ):=\left|2\mathrm{Pr}\left[{\mathbf{G}}_{\Pi ,\mathcal{A}}^{\mathrm{oram}\text{-}\mathrm{off}}(\lambda )=1\right]-1\right|$$

is negligible; statistical and perfect security are defined as for online ORAMs. Every online ORAM yields an offline ORAM with the same overhead — folklore.

Offline ORAM with fixed instructions

An offline ORAM with fixed instructions learns the whole operation sequence $\mathbf{o}=(o_1,\dots ,o_q)$ before processing starts, written blocks included: ${\mathsf{Acc}}_j$ and $\mathsf{Out}$ take the current operation $o_t$ together with $\mathbf{o}$ in place of $o$. The virtual array starts with contents $D\in {\mathcal{B}}_1^{N_1}$ that the client sees only through its physical reads: with $N_2\ge N_1$ and ${\mathcal{B}}_1\subseteq {\mathcal{B}}_2$, the physical array starts as $M_2=(D[1],\dots ,D[N_1],b_0,\dots ,b_0)$, and the correct answer to a read $i$ with no earlier write to $i$ is $D[i]$ in place of $\perp$. Bandwidth blowup and client storage are maximized over $D$ as well as over the sequence. From an empty array, the client could answer every read from $\mathbf{o}$ alone. BN16’s offline programs fix every fetch and store instruction in advance, the value of every store included — BN16.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{oram\text{-}fix}}_{\Pi,\calA}(\secpar)$}
\begin{algorithmic}
\State $K \gets \Gen(1^\secpar)$; $b \getsr \bits$
\State $((D_0, \mathbf{o}_0), (D_1, \mathbf{o}_1), \stA) \gets \calA(1^\secpar)$
\Comment{$D_0, D_1 \in \calB_1^{N_1}$; $\mathbf{o}_0, \mathbf{o}_1 \in \Ops_1^q$ for the same $q$}
\State $M_2 \gets (D_b[1], \ldots, D_b[N_1], b_0, \ldots, b_0)$
\State process $\mathbf{o}_b$ under $K$ from $\st = \bot$ and $M_2$, giving $\Acc_j$ and $\Out$ all of $\mathbf{o}_b$
\State $\mathit{ap} \gets (\mathrm{ap}(o_1), \ldots, \mathrm{ap}(o_q))$ for the operations of $\mathbf{o}_b$
\State $b' \gets \calA(\stA, \mathit{ap})$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

An offline ORAM $\Pi$ with fixed instructions is secure if it is $(1-\mathrm{negl}(\lambda ))$-correct for every $D\in {\mathcal{B}}_1^{N_1}$, with the answers $D[i]$ above, and for all efficient $\mathcal{A}$,

$${\mathbf{Adv}}_{\Pi ,\mathcal{A}}^{\mathrm{oram}\text{-}\mathrm{fix}}(\lambda ):=\left|2\mathrm{Pr}\left[{\mathbf{G}}_{\Pi ,\mathcal{A}}^{\mathrm{oram}\text{-}\mathrm{fix}}(\lambda )=1\right]-1\right|$$

is negligible; statistical and perfect security are defined as for online ORAMs.

Sublogarithmic-overhead offline ORAM with fixed instructions

A sublogarithmic-overhead offline ORAM with fixed instructions is a secure offline ORAM with fixed instructions, with any encoding of the data, whose physical cells have the size of its blocks (${\beta }_2={\beta }_1=w$), with $O(1)$ blocks of client memory at every step (Efficiency), block length $w\in \Omega (\log N_1)\cap N_1^{o(1)}$, and amortized bandwidth blowup $o(\log N_1)$ over every sequence of $q$ operations with $\lambda \le N_1\le q\le \mathrm{poly}(\lambda )$. BN16’s client likewise has a constant number of registers — BN16. Bounding only the client storage, the state kept between operations, would admit a client that, every $N_1$ operations, reads all of $D$ in one round and in the next writes the answers of the next $N_1$ operations to $N_1$ cells, one per operation, which each of those operations then reads: a fixed access pattern with $O(1)$ amortized bandwidth blowup. Small sorting circuits give a sublogarithmic-overhead offline ORAM with fixed instructions (Small sorting circuits ⇒ sublogarithmic-overhead offline ORAM with fixed instructions), and proving that none exists would need a superlinear lower bound on the size of sorting circuits — BN16. The construction relies on the store values being fixed in advance, and BN16 pose its extension to a more expressive offline class as an open question, so it is not known to give an offline ORAM that learns each written block only with its operation — BN16.

Balls-and-bins ORAM

In a balls-and-bins ORAM, ${\mathcal{B}}_2={\mathcal{B}}_1\cup \{b_0\}$, so each physical cell holds one virtual block (a ball) or the empty marker $b_0$. The client holds balls together with metadata that does not depend on ball contents. A physical read copies the cell’s ball into client memory, and a physical write stores $b_0$ or a ball the client holds. Which physical operations are issued depends only on $K$, the client’s coins, the metadata, and the indices and types of the virtual operations, never on ball contents: the ORAM moves balls and never encodes them — GO96, BN16. A balls-and-bins ORAM does not duplicate balls if it never keeps two copies of a ball, at the server or the client — CDH20.

Sublogarithmic-overhead balls-and-bins ORAM

A sublogarithmic-overhead balls-and-bins ORAM is a statistically secure offline balls-and-bins ORAM with $O(1)$ blocks of client memory at every step and amortized bandwidth blowup $o(\log N_1)$ over sequences of $q\ge N_1$ operations. None exists (No reduction from ORAM to sublogarithmic-overhead balls-and-bins ORAM) — GO96.

One-round ORAM

A one-round ORAM is an ORAM with $r=1$: all physical operations for a virtual operation are chosen before any of them is answered, so no physical address issued while processing $o$ depends on a block read while processing $o$.

Sub-square-root one-round balls-and-bins ORAM

A sub-square-root one-round balls-and-bins ORAM is a statistically secure one-round balls-and-bins ORAM that does not duplicate balls, with worst-case bandwidth blowup $o(\sqrt{N_1})$ and client storage of $o(\sqrt{N_1})$ blocks. None exists (No reduction from ORAM to sub-square-root one-round balls-and-bins ORAM) — CDH20.

Polylogarithmic-overhead ORAM

A polylogarithmic-overhead ORAM is a secure ORAM with block length ${\beta }_1\ge {\log }_2{N}_1$, client storage of $O(1)$ blocks and amortized bandwidth blowup $\mathrm{polylog}(N_1)$ over every sequence of $q$ operations with $\lambda \le N_1\le q\le \mathrm{poly}(\lambda )$, whose key $K\leftarrow \mathsf{Gen}(1^{\lambda })$ has length a fixed polynomial in $\lambda$, independent of $N_1$.

Logarithmic-overhead ORAM

A logarithmic-overhead ORAM is a secure ORAM with block length ${\log }_2{N}_1\le {\beta }_1=O(\log N_1)$, client storage of $O(1)$ blocks and amortized bandwidth blowup $O(\log N_1)$ over every sequence of $q$ operations with $\lambda \le N_1\le q\le \mathrm{poly}(\lambda )$, whose key $K\leftarrow \mathsf{Gen}(1^{\lambda })$ has length a fixed polynomial in $\lambda$, independent of $N_1$. One exists if a PRF does (PRF ⇒ logarithmic-overhead ORAM (OptORAMa)) — AKL+20.

Sublogarithmic-overhead ORAM

A sublogarithmic-overhead ORAM is a secure online ORAM with $N_1$ blocks of ${\beta }_1$ bits and physical cells of any size ${\beta }_2$, whose client memory of $m:=|K|+{\max }_t|{\mathsf{st}}_t|$ bits satisfies ${\beta }_1\le m\le N_1^{1-\epsilon }$ for a constant $\epsilon >0$, and whose amortized bandwidth blowup is $o(\log N_1)$. None exists (No reduction from ORAM to sublogarithmic-overhead ORAM) — LN18.

ORAM with server computation

In an ORAM with server computation, ${\mathsf{Ops}}_2$ also contains evaluation requests $(f,i_1,\dots ,i_k,i^{\prime })$ for $f$ in a fixed class $\mathcal{F}$ of efficiently computable functions ${\mathcal{B}}_2^k\to {\mathcal{B}}_2$, on which the server sets $M_2[i^{\prime }]\leftarrow f(M_2[i_1],\dots ,M_2[i_k])$. The adversary is a semi-honest server: in the security game, ${\mathcal{O}}_b$ returns its entire view, every physical operation with its contents together with $M_2$, in place of $\mathrm{ap}(o_b)$. The bandwidth counts the bits the client sends and receives, request descriptions included, and not the server’s work.

Constant-bandwidth ORAM

A constant-bandwidth ORAM is an efficient ORAM with server computation, secure against a semi-honest server, with worst-case bandwidth blowup $O(1)$ and client storage of $\mathrm{polylog}(N_1)$ blocks, for some block length ${\beta }_1\le \mathrm{poly}(\lambda ,\log N_1)$. Onion ORAM is one if DCR holds (DCR ⇒ constant-bandwidth ORAM (Onion ORAM)) — DDF+16.

Other results

• Every statistically secure balls-and-bins ORAM with $O(1)$ blocks of client memory at every step, even an offline one, has amortized bandwidth blowup $\Omega (\log N_1)$ (No reduction from ORAM to sublogarithmic-overhead balls-and-bins ORAM) — GO96. For offline ORAMs with fixed instructions that may encode the data, such a bound would imply superlinear lower bounds on the size of sorting circuits (Small sorting circuits ⇒ sublogarithmic-overhead offline ORAM with fixed instructions) — BN16.

• Every online ORAM with client memory $m\le N_1^{1-\epsilon }$ has amortized bandwidth blowup $\Omega (\log N_1)$, even with computational security and an arbitrary encoding of the data (No reduction from ORAM to sublogarithmic-overhead ORAM) — LN18. The bound holds even against a server that does not know which physical operations belong to which virtual operation — HKKS19.

• Every online ORAM makes $\Omega (\log (Nw/m)/\log (b/w))$ amortized memory probes per operation, where $N$ is the number of virtual cells, $w$ and $b$ the virtual and physical cell sizes and $m$ the client storage in bits; the bound is tight up to the $\log (b/w)$ factor and extends to non-colluding servers. For $w=\log N$ and $b,m\in \mathrm{polylog}N$, some offline ORAM makes $o(1)$ probes per operation on average while every online one makes $\Omega (\log N/\log \log N)$, the first separation of online and offline ORAM for any parameters — KL21.

• An online ORAM whose server only stores data and whose reads, but not writes, have $o(\log N_1)$ overhead follows from small sorting circuits together with locally decodable codes with parameters not known to exist, so a lower bound for online read-only ORAM would need a new circuit lower bound or would rule out such codes. LN18’s bound leaves online read-only ORAM open, while GO96’s balls-and-bins bound extends to offline and read-only ORAM — WW18.

• Every one-round balls-and-bins ORAM that does not duplicate balls has $\Omega (\sqrt{N_1})$ bandwidth or $\Omega (\sqrt{N_1})$ client memory (No reduction from ORAM to sub-square-root one-round balls-and-bins ORAM) — CDH20.

• The hierarchical ORAM has polylogarithmic overhead given a PRF (PRF ⇒ polylogarithmic-overhead ORAM (hierarchical ORAM)) — GO96. OptORAMa has $O(\log N_1)$ amortized bandwidth blowup given a PRF (PRF ⇒ logarithmic-overhead ORAM (OptORAMa)) — AKL+20, improving the $O(\log N_1\cdot \log \log N_1)$ of PanORAMa — PPRY18.

• A coin-flipping RAM simulates any RAM obliviously and online with polylogarithmic slowdown in time and space and no cryptographic assumption; with $n$ memory locations it fails with probability at most $n^{-\log n}$ — Ajt10.

• There is an ORAM whose access pattern is perfectly hidden, in the information-theoretic sense, without a random oracle, and DMN11 lower-bound the randomness an information-theoretically secure ORAM needs — DMN11.

• There is a statistically secure ORAM with $\tilde{O}({\log }^2{N}_1)$ overhead — CLP14, building on the tree-based ORAM of SCSL11, which has polylogarithmic worst-case cost with constant client storage — SCSL11.

• Path ORAM is statistically secure, encryption of the blocks aside. With the position map on the client, each access reads and writes one root-to-leaf path of its tree, $2Z\log N_1$ blocks for buckets of $Z=O(1)$ blocks — SDS+13. With blocks of $X\log N_1$ bits for $X\ge 2$ and the position map stored recursively in smaller Path ORAMs, there are two parameter sets, according to where the stashes of the recursive levels are kept, and each fails, by overflowing a stash, with probability $N_1^{-\omega (1)}$ — SDS+13:

  Stashes kept	Bandwidth blowup	Client storage (blocks)
  on the client	$O({\log }^2{N}_1/\log X)$	$O({\log }^2{N}_1/\log X)\cdot \omega (1)$
  on the server	$O({\log }^2{N}_1/\log X)\cdot \omega (1)$	$O(\log N_1)\cdot \omega (1)$

• For a RAM with $N$ words of $N^{\epsilon }$ bits, for a constant $0<\epsilon <1$, Circuit ORAM gives an ORAM with $O(1)$ words of client storage that runs $T$ steps in time $O(T\log N)\cdot \omega (1)$ with negligible statistical failure probability, or $O(T\log N)$ with inverse-polynomial failure probability, showing that the Goldreich–Ostrovsky bound is tight for some parameter ranges. For blocks of $D=\Omega ({\log }^{2}N)$ bits its circuit size is $O(D\log N)\cdot \omega (1)$ with failure probability $\mathrm{negl}(N)$ — WCS15.

• There is an oblivious parallel RAM compiler with polylogarithmic slowdown in total and parallel complexity whose memory-access distribution is statistically close to one independent of the data, and from it and IBE a garbled parallel RAM compiler — BCP16.

• Garbled RAM, which garbles a RAM program, its input and its memory so that the access pattern stays hidden too, exists if IBE does (IBE ⇒ garbled RAM) — GHL+14, and if one-way functions do, using them only as a black box (OWF ⇒ garbled RAM (black-box)) — GLO15.

• Functions that a RAM computes in sublinear time have secure two-party computation in amortized sublinear time: the parties run generic secure two-party computation on top of an ORAM, each keeping state essentially linear in its own input, and the optimized protocol combines Yao’s garbled circuits with the ORAM of SCSL11 — GKK+12, building on an idea of OS97.

• Private information storage gives private reads and writes to data held by several non-communicating databases, with information-theoretic privacy: any retrieval-only $k$-database scheme with communication $R(k,n)$ yields a $(k+1)$-database read/write scheme with communication $O(R(k,n)\cdot (\log n{)}^{O(1)})$, and no sublinear bounds for private information storage were known before — OS97.

• Floram is a distributed ORAM for two-party secure computation built from the function secret sharing of BGI15; it needs much less secure computation per access, at the cost of $O(n)$ local memory operations, and outperforms Circuit ORAM and square-root ORAM for datasets of 32 KiB or more — DS17.

Participates in

Produces Oblivious RAM

• DCR ⇒ constant-bandwidth ORAM (Onion ORAM) (via Constant-bandwidth ORAM)
• PRF ⇒ logarithmic-overhead ORAM (OptORAMa) (via Logarithmic-overhead ORAM)
• PRF ⇒ polylogarithmic-overhead ORAM (hierarchical ORAM) (via Polylogarithmic-overhead ORAM)
• Small sorting circuits ⇒ sublogarithmic-overhead offline ORAM with fixed instructions (via Sublogarithmic-overhead offline ORAM with fixed instructions)

Barriers

• No reduction from ORAM to sub-square-root one-round balls-and-bins ORAM
• No reduction from ORAM to sublogarithmic-overhead balls-and-bins ORAM
• No reduction from ORAM to sublogarithmic-overhead ORAM