Oblivious RAM
This definition is suited for settings like protected programs running on unprotected shared memory or clients running programs on their systems by accessing previously stored data on a remote server.
[1] A Turing machine (TM), a mathematical abstraction of a real computer (program), is said to be oblivious if, for any two inputs of the same length, the motions of the tape heads remain the same.
Pippenger and Fischer[2] proved that every TM with running time
In the RAM model of computation, there is a CPU that can execute the basic mathematical, logical, and control instructions.
The CPU is also associated with a few registers and a physical random access memory, where it stores the operands of its instructions.
The definition of ORAMs captures a similar notion of obliviousness for memory accesses in the RAM model.
This description will still make sense if the CPU is replaced by a client with a small storage and the physical RAM is replaced with a remote server with a large storage capacity, where the data of the client resides.
during its execution is called its memory access pattern and is denoted by
such that the following properties hold: Note that the above definition uses the notion of statistical security.
[3] ORAMs were introduced by Goldreich and Ostrovsky,[4][5][1] where the key motivation was stated as providing software protection from an adversary who can observe a program's memory access pattern (but not the contents of the memory).
The main result in this work[1] is that there exists an ORAM compiler that uses
Another important attribute of an ORAM construction is whether the access overhead is amortized or worst-case.
Several earlier ORAM constructions have good amortized access overhead guarantees but have
Some ORAM constructions with polylogarithmic worst-case computational overheads are.
[7][8][9][10][11][12] The constructions of[4][5][1] were in the random oracle model, where the client assumes access to an oracle that behaves like a random function and returns consistent answers for repeated queries.
One of the only known lower bounds on the access overhead of ORAMs is due to Goldreich et al.[1] They show a
[15] There is also a conditional lower bound on the access overhead of ORAMs due to Boyle et al.[16] that relates this quantity with that of the size of sorting networks.
A trivial ORAM simulator construction, for each read or write operation, reads from and writes to every single element in the array, only performing a meaningful action for the address specified in that single operation.
The trivial solution thus, scans through the entire memory for each operation.
A simple version of a statistically secure ORAM compiler constructed by Chung and Pass[3] is described in the following along with an overview of a proof of its correctness.
It may be noted that this construction can be made to work even for memory requests coming in an online fashion.
This data structure, for each block b, stores the leaf of T associated with b in
Describing the procedures, Owrite and Oread is enough to complete the description of Π′.
and the value v to be stored at the location l. It has three main phases, namely FETCH, PUT_BACK, and FLUSH.
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
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.
denote the execution of the program Π on an input x using n memory cells.
During each Oread and Owrite operation, two random root-to-leaf paths of T are fully explored by Π′.
The total memory used up by Π′ is equal to the size of T. Each triple stored in the tree has
