Oblivious RAM (ORAM)

Oblivious RAM (ORAM) was first introduced by [GO96]. It is a primitive that provides a generic compilation of any random-access memory (RAM) program to one which hides the accesses pattern of the underlying RAM.

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

Formal Definition

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 $\bot \in {\mathsf {StSp}}$ and $\bot \not \in {\mathcal {B}}_{1}$.

Furthermore, we define the sets ${\mathsf {RdOps}}_{j}=[N_{j}],{\mathsf {WrOps}}_{j}=[N_{j}]\times {\mathcal {B}}_{j},{\text{ and }}{\mathsf {Ops}}_{j}={\mathsf {RdOps}}_{j}\cup {\mathsf {WrOps}}_{j}$. These are the allowed opertations for the virtual array ($j=1$) and the physical array ($j=2$).

Syntax

An $r$-round Oblivious RAM (ORAM) is a tuple of efficient functions $({\mathsf {Gen}},{\mathsf {Access}}_{1},\ldots ,{\mathsf {Access}}_{r},{\mathsf {Out}})$ such that:

• ${\mathsf {Gen}}(1^{\lambda })\to k$, is a randomized algorithm that takes a security parameter, and outputs a key $k\in {\mathsf {KSp}}$,
• ${\mathsf {Access}}_{i}:{\mathcal {B}}_{2}^{*}\times {\mathsf {KSp}}\times {\mathsf {Ops}}_{1}\times {\mathsf {StSp}}\times \to {\mathsf {RdOps}}_{2}^{*}$, is a deterministic algorithm for the $i$th round fo the ORAM's operation that takes as input a key, a virtual operation, and a state, and outputs zero or more physical read operations. (for $i=1,\ldots ,r)$
• ${\mathsf {Out}}:{\mathcal {B}}_{2}^{*}\times {\mathsf {KSp}}\times {\mathsf {Ops}}_{1}\times {\mathsf {StSp}}\times \to ({\mathcal {B}}_{1}\cup \{\bot \})\times {\mathsf {WrOps}}_{2}^{*}\times {\mathsf {StSp}}$ is a deterministic algorithm for the final output of the ORAM operation processing, which takes as input a key, a virtual operation, and a state, and outputs a virtual block (or $\bot$), zero or more write operations, and an updated state.

The above functions describe the processing of the Oblivious RAM query. They are used in the following way to process a query at index $i$:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \underline{\mathsf{Access}(k,\mathsf{op},\mathsf{st})} \text{\bf d}_r \gets \bot\\ \text{For} i=1,\ldots,r\\ \quad \mathsf{rds} \gets \mathsf{rds} \cup \mathsf{Access}_i(\text{\bf d}_r,k,\mathsf{op},\mathsf{st})\\ \quad \text{\bf d}_r \gets \text{\bf M}_2[\mathsf{rds}]\\ \text{Return} \mathsf{rds} \end{align} }

Security

An ORAM is secure if for all efficient $D$, there exists a negligible function $\nu$, such that

$TODO$

Impossibilities

• It is known that any Oblivious RAM over an array of $n$ elements must incur $\Omega (\log n)$ amortized overhead blow-up. Due to [GO96] and [LN18].
• It is known that any one-round balls-in-bins ORAM must have $\Omega ({\sqrt {n}})$ overhead or storage. Due to [CDH20]

Variations

• Oblivious Parallel RAM (OPRAM)
• Oblivious Single-Access Machines (OSAM)