View source for Oblivious RAM (ORAM)

<noinclude>
[[Category:Primitives]]
[[Category:Unconditional]]
[[Category:Minicrypt]]

[[Oblivious RAM (ORAM)]] was first introduced by [[ccref#go96|[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 [[SE|standard symmetric encryption]].

== Formal Definition ==
Throughout, we use the following notation. All oblivious RAM schemes are defined with respect to a key space <math>\mathsf{KSp}</math>, state space <math>\mathsf{StSp}</math>, virtual array size <math>N_1</math> and blocks <math>\mathcal{B}_1</math>, and physical array size <math>N_2</math> and blocks <math>\mathcal{B}_2</math>. We additionally assume <math>\bot\in \mathsf{StSp}</math> and <math>\bot \not\in\mathcal{B}_1</math>.

Furthermore, we define the sets <math>\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</math>. These are the allowed opertations for the virtual array (<math>j=1</math>) and the physical array (<math>j=2</math>).

=== Syntax ===
An <math>r</math>-round [[Oblivious RAM (ORAM)]] is a tuple of efficient functions <math>(\mathsf{Gen}, \mathsf{Access}_1,\ldots,\mathsf{Access}_r,\mathsf{Out})</math> such that:
* <math>\mathsf{Gen}(1^{\lambda}) \to k</math>, is a randomized algorithm that takes a security parameter, and outputs a key <math>k\in \mathsf{KSp}</math>,
* <math>\mathsf{Access}_i: \mathcal{B}_2^* \times \mathsf{KSp}\times \mathsf{Ops}_1 \times \mathsf{StSp} \times \to \mathsf{RdOps}_2^*</math>, is a deterministic algorithm for the <math>i</math>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 <math>i = 1,\ldots,r)</math>
* <math>\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}</math> 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 <math>\bot</math>), zero or more write operations, and an updated state.

TODO typical use of the above functions

=== Security ===
An [[ORAM]] is ''secure'' if for all efficient <math>D</math>, there exists a negligible function <math>\nu</math>, such that
<center><math>
TODO
</math></center>


== Impossibilities ==
* It is known that any Oblivious RAM over an array of <math>n</math> elements must incur <math>\Omega(\log n)</math> amortized overhead blow-up. Due to [[ccref#go96|[GO96]]] and [[ccref#ln18|[LN18]]].
* It is known that any one-round balls-in-bins ORAM must have <math>\Omega(\sqrt{n})</math> overhead or storage. Due to [[ccref#cdh20|[CDH20]]]

== Variations ==
* [[Oblivious Parallel RAM (OPRAM)]]
* [[Oblivious Single-Access Machines (OSAM)]]