1000/1000

Hot
Most Recent

Submitted Successfully!

To reward your contribution, here is a gift for you: A free trial for our video production service.

Thank you for your contribution! You can also upload a video entry or images related to this topic.

Do you have a full video?

Are you sure to Delete?

Cite

If you have any further questions, please contact Encyclopedia Editorial Office.

HandWiki. Oblivious Ram. Encyclopedia. Available online: https://encyclopedia.pub/entry/37776 (accessed on 07 August 2024).

HandWiki. Oblivious Ram. Encyclopedia. Available at: https://encyclopedia.pub/entry/37776. Accessed August 07, 2024.

HandWiki. "Oblivious Ram" *Encyclopedia*, https://encyclopedia.pub/entry/37776 (accessed August 07, 2024).

HandWiki. (2022, December 02). Oblivious Ram. In *Encyclopedia*. https://encyclopedia.pub/entry/37776

HandWiki. "Oblivious Ram." *Encyclopedia*. Web. 02 December, 2022.

Copy Citation

An Oblivious RAM (ORAM) simulator is a compiler that transforms algorithms in such a way that the resulting algorithms preserve the input-output behavior of the original algorithm but the distribution of memory access pattern of the transformed algorithm is independent of the memory access pattern of the original algorithm. The definition of ORAMs is motivated by the fact that an adversary can obtain nontrivial information about the execution of a program and the nature of the data that it is dealing with, just by observing the pattern in which various locations of memory are accessed during its execution. An adversary can get this information even if the data values are all encrypted. The definition suits equally well to the settings of protected programs running on unprotected shared memory as well as a client running a program on its system by accessing previously stored data on a remote server. The concept was formulated by Oded Goldreich in 1987.

original algorithm
shared memory
oram

A Turing machine (TM), the 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^{[1]} proved that every TM with running time [math]\displaystyle{ T(n) }[/math] can be made oblivious and that the running time of the oblivious TM is [math]\displaystyle{ O(T(n)\log T(n)) }[/math]. A more realistic model of computation is the RAM model. 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 CPU in addition has instructions to read the contents of a memory cell and write a specific value to a memory cell. The definition of ORAMs capture a similar notion of obliviousness memory accesses in this model.

Informally, an ORAM is an algorithm at the interface of a protected CPU and the physical RAM such that it acts like a RAM to the CPU by querying the physical RAM for the CPU while hiding information about the actual memory access pattern of the CPU from the physical RAM. In other words, the distribution of memory accesses of two programs that make the same number of memory accesses to the RAM are indistinguishable from each other. 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.

The following is a formal definition of ORAMs.^{[2]} Let [math]\displaystyle{ \Pi }[/math] denote a program requiring a memory of size [math]\displaystyle{ n }[/math] when executing on an input [math]\displaystyle{ x }[/math]. Suppose that [math]\displaystyle{ \Pi }[/math] has instructions for basic mathematical and control operations in addition to two special instructions [math]\displaystyle{ \mathsf{read}(l) }[/math] and [math]\displaystyle{ \mathsf{write}(l,v) }[/math], where [math]\displaystyle{ \mathsf{read}(l) }[/math] reads the value at location [math]\displaystyle{ l }[/math] and [math]\displaystyle{ \mathsf{write}(l,v) }[/math] writes the value [math]\displaystyle{ v }[/math] to [math]\displaystyle{ l }[/math]. The sequence of memory cell accessed by a program [math]\displaystyle{ \Pi }[/math] during its execution is called its memory access pattern and is denoted by [math]\displaystyle{ \tilde{\Pi}(n,x) }[/math].

A polynomial-time algorithm, [math]\displaystyle{ C }[/math] is an Oblivious RAM (ORAM) compiler with computational overhead [math]\displaystyle{ c(\cdot) }[/math] and memory overhead [math]\displaystyle{ m(\cdot) }[/math], if [math]\displaystyle{ C }[/math] given [math]\displaystyle{ n\in N }[/math] and a deterministic RAM program [math]\displaystyle{ \Pi }[/math] with memory-size [math]\displaystyle{ n }[/math] outputs a program [math]\displaystyle{ \Pi_0 }[/math] with memory-size [math]\displaystyle{ m(n)\cdot n }[/math] such that for any input [math]\displaystyle{ x }[/math], the running-time of [math]\displaystyle{ \Pi_0(n, x) }[/math] is bounded by [math]\displaystyle{ c(n)\cdot T }[/math] where [math]\displaystyle{ T }[/math] is the running-time of [math]\displaystyle{ \Pi(n, x) }[/math], and there exists a negligible function [math]\displaystyle{ \mu }[/math] such that the following properties hold:

**Correctness:**For any [math]\displaystyle{ n \in \mathbb{N} }[/math] and any string [math]\displaystyle{ x \in \{0, 1\}^* }[/math], with probability at least [math]\displaystyle{ 1- \mu(n) }[/math], [math]\displaystyle{ \Pi(n, x) = \Pi_0(n, x) }[/math].**Obliviousness:**For any two programs [math]\displaystyle{ \Pi_1, \Pi_2 }[/math], any [math]\displaystyle{ n \in \mathbb{N} }[/math] and any two inputs, [math]\displaystyle{ x_1, x_2 \in \{0, 1\}^* }[/math] if [math]\displaystyle{ |\tilde{\Pi}_1(n, x_1)| = |\tilde{\Pi}_2(n, x_2)| }[/math], then [math]\displaystyle{ {\tilde{\Pi}_1}'(n, x_1) }[/math] is [math]\displaystyle{ \mu }[/math]-close to [math]\displaystyle{ {\tilde{\Pi}_2}'(n, x_2) }[/math] in statistical distance, where [math]\displaystyle{ {\Pi_1}' = C(n, \Pi_1) }[/math] and [math]\displaystyle{ {\Pi_2}' = C(n, \Pi_2) }[/math].

Note that the above definition uses the notion of statistical security. One can also have a similar definition for the notion of computational security.

ORAMs were introduced by Goldreich and Ostrovsky^{[3]}^{[4]}^{[5]} where in the key motivation was stated as software protection from an adversary who can observe the memory access pattern (but not the contents of the memory).

The main result in this work^{[5]} is that there exists an ORAM compiler that uses [math]\displaystyle{ O(n) }[/math] server space and incurs a running time overhead of [math]\displaystyle{ 2^{O(\sqrt{\log n \log \log n})} }[/math] when making a program that uses [math]\displaystyle{ n }[/math] memory cells oblivious. This work initiated a series of works in the construction of oblivious RAMs that is going on till date. There are several attributes that need to be considered when we compare various ORAM constructions. The most important parameters of an ORAM construction are the amounts of client storage, the amount of server storage and the time overhead in making one memory access. Based on these attributes, the construction of Kushilevitz et al.^{[6]} is the best known ORAM construction. It achieves [math]\displaystyle{ O(1) }[/math] client storage, [math]\displaystyle{ O(n) }[/math] server storage and [math]\displaystyle{ o(\log^2 n) }[/math] access overhead.

Another important attribute of an ORAM construction is whether the access overhead is amortized or worst-case. Several of the earlier ORAM constructions have good amortized access overhead guarantees, but have [math]\displaystyle{ \Omega(N) }[/math] worst-case access overheads. Some of the ORAM constructions with polylogarithmic worst-case computational overheads are.^{[6]}^{[7]}^{[8]}^{[9]}^{[10]} The constructions of^{[3]}^{[4]}^{[5]} were for 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. They also noted that this oracle could be replaced by a pseudorandom function whose seed is a secret key stored by the client, if one assumes the existence of one-way functions. The papers^{[11]}^{[12]} were aimed at removing this assumption completely. The authors of^{[12]} also achieve an access overhead of [math]\displaystyle{ O(\log^3 n) }[/math], which is just a log-factor away from the best known ORAM access overhead.

While most of the earlier works focus on proving security computationally, there are more recent works^{[2]}^{[8]}^{[11]}^{[12]} that use the stronger statistical notion of security.

One of the only known lower bounds on the access overhead of ORAMs is due to Goldreich et al.^{[5]} They show a [math]\displaystyle{ \Omega(\log{n}) }[/math] lower bound for ORAM access overhead, where [math]\displaystyle{ n }[/math] is the data size. There is also a conditional lower bound on the access overhead of ORAMs due to Boyle et al.^{[13]} 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. This scheme incurs a time overhead of [math]\displaystyle{ \Omega(n) }[/math] for each memory operation, where n is the size of the memory.

A simple version of a statistically secure ORAM compiler constructed by Chung and Pass^{[2]} is described in the following along with an overview of the proof of its correctness. The compiler on input n and a program Π with its memory requirement n, outputs an equivalent oblivious program Π′.

If the input program Π uses r registers, the output program Π′ will need [math]\displaystyle{ r+n/{\alpha}+\text{poly}\log{n} }[/math] registers, where [math]\displaystyle{ \alpha\gt 1 }[/math] is a parameter of the construction. Π′ uses [math]\displaystyle{ O(n \text{ poly} \log n) }[/math] memory and its (worst-case) access overhead is [math]\displaystyle{ O(\text{poly}\log n) }[/math].

The ORAM compiler is very simple to describe. Suppose that the original program Π has instructions for basic mathematical and control operations in addition to two special instructions [math]\displaystyle{ \mathsf{read}(l) }[/math] and [math]\displaystyle{ \mathsf{write}(l,v) }[/math], where [math]\displaystyle{ \mathsf{read}(l) }[/math] reads the value at location l and [math]\displaystyle{ \mathsf{write}(l,v) }[/math] writes the value v to l. The ORAM compiler, when constructing Π′, simply replaces each read and write instructions with subroutines Oread and Owrite and keeps the rest of the program the same. It may be noted that this construction can be made to work even for memory requests coming in an online fashion.

The program Π′ stores a complete binary tree T of depth [math]\displaystyle{ d=\log (n/\alpha) }[/math] 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 [math]\displaystyle{ \gamma }[/math] are [math]\displaystyle{ \gamma_0 }[/math] and [math]\displaystyle{ \gamma_1 }[/math] 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 [math]\displaystyle{ \lceil n /\alpha \rceil }[/math] blocks in total. In other words, the memory cell r corresponds to block [math]\displaystyle{ b=\lfloor r/\alpha \rfloor }[/math].

At any point of 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 position map, denoted by [math]\displaystyle{ Pos }[/math], using [math]\displaystyle{ O(n/\alpha) }[/math] registers. This data structure, for each block b, stores the leaf of T associated with b in [math]\displaystyle{ Pos(b) }[/math].

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

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 [math]\displaystyle{ l \in [n] }[/math] 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. [math]\displaystyle{ b\leftarrow \lfloor l/ \alpha \rfloor }[/math] // b is the block containing l. [math]\displaystyle{ i\leftarrow l\mod \alpha }[/math] // i is l's component in the block b. [math]\displaystyle{ pos\leftarrow Pos(b) }[/math]if[math]\displaystyle{ pos =\perp }[/math]then[math]\displaystyle{ pos\leftarrow_R [n/ \alpha] }[/math]. // Set [math]\displaystyle{ pos }[/math] to a uniformly random leaf in T. flag [math]\displaystyle{ \leftarrow 0 }[/math].foreach node N on the path the path from root to [math]\displaystyle{ pos }[/math]doifN has a triple of the form [math]\displaystyle{ (b,pos,x) }[/math]thenRemove [math]\displaystyle{ (b,pos,x) }[/math] from N, store x in a register, and write back the updated N to T. flag [math]\displaystyle{ \leftarrow 1 }[/math].elseWrite back N to T.Procedure PUT_BACK// Add back the updated block at the root. [math]\displaystyle{ pos'\leftarrow_R [n/ \alpha] }[/math]. // Set [math]\displaystyle{ pos' }[/math] to a uniformly random leaf in T.ifflag[math]\displaystyle{ =1 }[/math]thenSet [math]\displaystyle{ x' }[/math] to be same as x except for v at the i-th position.elseSet [math]\displaystyle{ x' }[/math] to be a block with v at i-th position and ⊥'s everywhere else.ifthere is space left in the rootthenAdd the triple [math]\displaystyle{ (b,pos',x') }[/math] to the root of T.elseAbort outputtingoverflow.Procedure FLUSH// Push the blocks present in a random path as far down as possible. [math]\displaystyle{ pos^*\leftarrow_R [n/ \alpha] }[/math]. // Set [math]\displaystyle{ pos^* }[/math] to a uniformly random leaf in T.foreach triple [math]\displaystyle{ (b'',pos'',v'') }[/math] in the nodes traversed the path from root to [math]\displaystyle{ pos^* }[/math] Push down this triple to the node N that corresponds to the longest common prefix of [math]\displaystyle{ pos'' }[/math] and [math]\displaystyle{ pos^* }[/math].ifat any point some bucket is about to overflowthenAbort outputtingoverflow.

The task of the FETCH phase is to look for the location l in the tree T. Suppose [math]\displaystyle{ pos }[/math] is the leaf associated with the block containing location l. For each node N in T on the path from root to [math]\displaystyle{ pos }[/math], 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, 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 [math]\displaystyle{ pos^* }[/math] and then tries to push down every node as much as possible along the path from root to [math]\displaystyle{ pos^* }[/math]. 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 [math]\displaystyle{ l \in [n] }[/math] and it is almost the same as Owrite. In the FETCH stage, if it does not find a triple corresponding to the 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.

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

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

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 [math]\displaystyle{ \Pi_1 }[/math] and [math]\displaystyle{ \Pi_2 }[/math] and two inputs [math]\displaystyle{ x_1,x_2 \in \{0,1\}^* }[/math] such that [math]\displaystyle{ |\tilde{\Pi_1}(x_1,n)| = |\tilde{\Pi_2}(x_2,n)| }[/math], with probability at least [math]\displaystyle{ 1 - 2\mu(n) }[/math], the access patterns [math]\displaystyle{ \tilde{\Pi_1'}(x_1,n) }[/math] and [math]\displaystyle{ \tilde{\Pi_2'}(x_2,n) }[/math] are identical.

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

- Overflow Lemma
- There exists a negligible function μ such that for very program Π, every n and input x, the program [math]\displaystyle{ \Pi'(n,x) }[/math] outputs overflow with probability at most [math]\displaystyle{ \mu(n) }[/math].

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

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

- Nicholas Pippenger and Michael J. Fischer. 1979. Relations among complexity measures. Journal of ACM. DOI = http://dl.acm.org/citation.cfm?id=322138
- Kai-Min Chung and Rafael Pass. 2013. A simple ORAM. IACR Cryptology ePrint Archive. DOI = http://eprint.iacr.org/2013/243
- Oded Goldreich. 1987. Towards a theory of software protection and simulation by oblivious RAMs. In Proceedings of the nineteenth annual ACM symposium on Theory of computing (STOC '87), Alfred V. Aho (Ed.). ACM, New York, NY, USA, 182-194. doi:10.1145/28395.28416 https://doi.org/10.1145%2F28395.28416
- Rafail Ostrovsky. Efficient computation on oblivious rams. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13–17, 1990.
- Oded Goldreich and Rafail Ostrovsky. Software protection and simulation on oblivious rams. Journal of ACM.1996
- Eyal Kushilevitz, Steve Lu, and Rafail Ostrovsky. On the (in) security of hash-based oblivious ram and a new balancing scheme. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms. 2012
- Rafail Ostrovsky and Victor Shoup. Private information storage (extended abstract). In Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing. 1997.
- Elaine Shi, T-H Hubert Chan, Emil Stefanov, and Mingfei Li. Oblivious ram with [math]\displaystyle{ O((\log n)^3) }[/math] worst-case cost. In Advances in Cryptology. ASIACRYPT 2011.
- Michael T. Goodrich, Michael Mitzenmacher, Olga Ohrimenko, and Roberto Tamassia. Oblivious ram simulation with efficient worst-case access overhead. In Proceedings of the 3rd ACM workshop on Cloud computing security workshop. 2011.
- Kai-Min Chung, Zhenming Liu, and Rafael Pass. Statistically-secure ORAM with [math]\displaystyle{ \tilde(\log^2 n) }[/math] overhead. In Advances in Cryptology - ASIACRYPT 2014.
- Miklos Ajtai. Oblivious rams without cryptographic assumptions. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC. 2010
- Ivan Damgard, Sigurd Meldgaard, and Jesper Buus Nielsen. Perfectly secure oblivious RAM without random oracles. In Theory of Cryptography Conference, TCC. 2011
- Elette Boyle and Moni Naor. Is there an oblivious RAM lower bound? In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science. 2016.

More

Information

Subjects:
Computer Science, Theory & Methods

Contributor
MDPI registered users' name will be linked to their SciProfiles pages. To register with us, please refer to https://encyclopedia.pub/register
:

View Times:
346

Entry Collection:
HandWiki

Update Date:
02 Dec 2022