{{Multiple issues| {{tone|date=December 2015}} {{more footnotes needed|date=December 2015}} {{Technical|date=December 2015}} }} An '''Oblivious RAM (ORAM) simulator''' is a compiler that transforms an algorithm in such a way that the resulting algorithm preserves the input-output behavior of the original algorithm but the distribution of the memory access patterns of the transformed algorithm is independent of the memory access pattern of the original algorithm.
The use of ORAMs is motivated by the fact that an adversary can obtain nontrivial information about the execution of a program and the data that the program is using just by observing the pattern in which the program accesses various memory locations during its execution. An adversary can get this information even if the data in memory is encrypted.
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. The concept was formulated by Oded Goldreich and Rafail Ostrovsky in 1996.<ref name="GO96" />
==Definition==
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<ref>{{citation|last1=Pippenger|first1=Nicholas|author1-link=Nick Pippenger|last2=Fischer|first2=Michael J.|author2-link=Michael J. Fischer|doi=10.1145/322123.322138|issue=2|journal=Journal of the ACM|mr=528038|pages=361–381|title=Relations among complexity measures|volume=26|year=1979|s2cid=2432526 |doi-access=free}}</ref> proved that every TM with running time <math>T(n)</math> can be made oblivious and that the running time of the oblivious TM is <math>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 also has instructions to read the contents of a memory cell and write a specific value to a memory cell. The definition of ORAMs captures a similar notion of obliviousness for memory accesses in the RAM 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 is 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. Let <math>\Pi</math> denote a program requiring memory of size <math>n</math> when executing on an input <math>x</math>. Suppose that <math>\Pi</math> has instructions for basic mathematical and control operations in addition to two special instructions <math>\mathsf{read}(l)</math> and <math>\mathsf{write}(l,v)</math>, where <math>\mathsf{read}(l)</math> reads the value at location <math>l</math> and <math>\mathsf{write}(l,v)</math> writes the value <math>v</math> to <math>l</math>. The sequence of memory cells accessed by a program <math>\Pi</math> during its execution is called its memory access pattern and is denoted by <math>\tilde{\Pi}(n,x)</math>.
A polynomial-time algorithm <math>C</math> is an Oblivious RAM (ORAM) compiler with computational overhead <math>c(\cdot)</math> and memory overhead <math>m(\cdot)</math>, if <math>C</math> given <math>n\in N</math> and a deterministic RAM program <math>\Pi</math> with memory-size <math>n</math> outputs a program <math>\Pi_0</math> with memory-size <math>m(n)\cdot n</math> such that for any input <math>x</math>, the running-time of <math>\Pi_0(n, x)</math> is bounded by <math>c(n)\cdot T</math> where <math>T</math> is the running-time of <math>\Pi(n, x)</math>, and there exists a negligible function <math>\mu</math> such that the following properties hold: * '''Correctness:''' For any <math>n \in \mathbb{N}</math> and any string <math>x \in \{0, 1\}^*</math>, with probability at least <math>1- \mu(n)</math>, <math>\Pi(n, x) = \Pi_0(n, x)</math>. *'''Obliviousness:''' For any two programs <math>\Pi_1, \Pi_2</math>, any <math>n \in \mathbb{N}</math> and any two inputs, <math>x_1, x_2 \in \{0, 1\}^*</math> if <math>|\tilde{\Pi}_1(n, x_1)| = |\tilde{\Pi}_2(n, x_2)|</math>, then <math>{\tilde{\Pi}_1}'(n, x_1)</math> is <math>\mu</math>-close to <math>{\tilde{\Pi}_2}'(n, x_2)</math> in statistical distance, where <math>{\Pi_1}' = C(n, \Pi_1)</math> and <math>{\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.<ref name="CP13">{{citation |last1=Chung |first1=Kai-Min |title=A simple ORAM |url=https://eprint.iacr.org/2013/243 |work=IACR Cryptology ePrint Archive |year=2013 |last2=Pass |first2=Rafael}}</ref>
==History of ORAMs==
ORAMs were introduced by Goldreich and Ostrovsky,<ref name = "G87">{{citation|last=Goldreich|first=Oded|authorlink=Oded Goldreich|editor-last=Aho|editor-first=Alfred V.|editor-link=Alfred Aho|contribution=Towards a theory of software protection and simulation by oblivious RAMs|doi=10.1145/28395.28416|pages=182–194|publisher=Association for Computing Machinery|title=Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC '87)|year=1987|isbn=0-89791-221-7 |s2cid=17767715 }}</ref><ref name="O90">{{citation|last=Ostrovsky|first=Rafail|author-link=Rafail Ostrovsky|contribution=Efficient computation on oblivious RAMs|doi=10.1145/100216.100289|pages=514–523|publisher=Association for Computing Machinery|title=Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC '90)|year=1990|s2cid=11987830 |doi-access=free|isbn=0-89791-361-2 }}</ref><ref name="GO96">{{citation|last1=Goldreich|first1=Oded|author1-link=Oded Goldreich|last2=Ostrovsky|first2=Rafail|author2-link=Rafail Ostrovsky|doi=10.1145/233551.233553|issue=3|journal=Journal of the ACM|mr=1408562|pages=431–473|title=Software protection and simulation on oblivious RAMs|volume=43|year=1996|hdl=1721.1/103684|s2cid=7502114 |hdl-access=free}}</ref> 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<ref name="GO96"/> is that there exists an ORAM compiler that uses <math>O(n)</math> server space and incurs a running time overhead of <math>{O(\log^3 n)}</math> when making a program that uses <math>n</math> memory cells oblivious. There are several attributes that need to be considered when comparing various ORAM constructions. The most important parameters of an ORAM construction's performance are the client-side space overhead, server-side space overhead, and the time overhead required to make one memory access. Based on these attributes, the construction of Asharov et al.,<ref name = "OptORAMa">{{citation|last1=Asharov|first1=Gilad|last2=Komargodski|first2=Ilan|last3=Lin|first3=Wei-Kai|last4=Nayak|first4=Kartik|last5=Peserico|first5=Enoch|last6=Shi|first6=Elaine|contribution=OptORAMa: Optimal Oblivious RAM|doi=10.1145/3566049|pages=4:1–4:70|publisher=Association for Computing Machinery|title=Journal of the ACM|year=2023|volume=70 }}</ref> called "OptORAMa", is the first optimal ORAM construction. It achieves <math>O(1)</math> client storage, <math>O(n)</math> server storage, and <math>O(\log n)</math> access overhead, matching the known lower bounds.
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 <math>\Omega(N)</math> worst-case access overheads. Some ORAM constructions with polylogarithmic worst-case computational overheads are.<ref name = "AsharovKLS23">{{citation|last1=Asharov|first1=Gilad|last2=Komargodski|first2=Ilan|last3=Lin|first3=Wei-Kai|last4=Shi|first4=Elaine|contribution=Oblivious {RAM} with Worst-Case Logarithmic Overhead|doi=10.1007/s00145-023-09447-5|pages=7|publisher=Springer|title=Journal of Cryptology|year=2023}}</ref><ref name ="KLO12">{{citation|last1=Kushilevitz|first1=Eyal|last2=Lu|first2=Steve|last3=Ostrovsky|first3=Rafail|author3-link=Rafail Ostrovsky|contribution=On the (in)security of hash-based oblivious RAM and a new balancing scheme|doi=10.1137/1.9781611973099.13|mr=3205204|pages=143–156|publisher=Association for Computing Machinery|title=Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms|year=2012|doi-access=free|isbn=978-1-61197-210-8 }}</ref><ref name="OS97">{{citation|last1=Ostrovsky|first1=Rafail|author1-link=Rafail Ostrovsky|last2=Shoup|first2=Victor|author2-link=Victor Shoup|editor1-last=Leighton|editor1-first=F. Thomson|editor1-link=F. Thomson Leighton|editor2-last=Shor|editor2-first=Peter W.|editor2-link=Peter Shor|contribution=Private information storage (extended abstract)|doi=10.1145/258533.258606|pages=294–303|publisher=Association for Computing Machinery|title=Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing (STOC '97)|year=1997|isbn=0-89791-888-6 |s2cid=14488066 }}</ref><ref name ="SCSL11">{{citation|last1=Shi|first1=Elaine|author1-link= Elaine Shi |last2=Chan|first2=T.-H. Hubert|last3=Stefanov|first3=Emil|last4=Li|first4=Mingfei|editor1-last=Lee|editor1-first=Dong Hoon|editor2-last=Wang|editor2-first=Xiaoyun|contribution=Oblivious RAM with <math>O((\log N)^3)</math> worst-case cost|doi=10.1007/978-3-642-25385-0_11|pages=197–214|publisher=Springer|series=Lecture Notes in Computer Science|title=Advances in Cryptology – ASIACRYPT 2011 – 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, December 4–8, 2011, Proceedings|volume=7073|year=2011|doi-access=free|hdl=10722/139993|isbn=978-3-642-25384-3 |hdl-access=free}}</ref><ref name ="GMOT11">{{citation|last1=Goodrich|first1=Michael T.|author1-link=Michael T. Goodrich|last2=Mitzenmacher|first2=Michael|author2-link=Michael Mitzenmacher|last3=Ohrimenko|first3=Olga|last4=Tamassia|first4=Roberto|author4-link=Roberto Tamassia|editor1-last=Cachin|editor1-first=Christian|editor2-last=Ristenpart|editor2-first=Thomas|contribution=Oblivious RAM simulation with efficient worst-case access overhead|doi=10.1145/2046660.2046680|pages=95–100|publisher=Association for Computing Machinery|title=Proceedings of the 3rd ACM Cloud Computing Security Workshop, CCSW 2011, Chicago, IL, USA, October 21, 2011|year=2011|s2cid=72429 |arxiv=1107.5093|isbn=978-1-4503-1004-8 }}</ref><ref name ="CLP14">{{citation|last1=Chung|first1=Kai-Min|last2=Liu|first2=Zhenming|last3=Pass|first3=Rafael|editor1-last=Sarkar|editor1-first=Palash|editor2-last=Iwata|editor2-first=Tetsu|contribution=Statistically-secure ORAM with <math>\tilde{O}(\log^2 n)</math> overhead|doi=10.1007/978-3-662-45608-8_4|pages=62–81|publisher=Springer|series=Lecture Notes in Computer Science|title=Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014, Proceedings, Part II|volume=8874|year=2014|doi-access=free|arxiv=1307.3699|isbn=978-3-662-45607-1 }}</ref> The constructions of<ref name ="G87" /><ref name ="O90" /><ref name ="GO96" /> 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. Access to the 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<ref name ="A10">{{citation|last=Ajtai|first=Miklós|authorlink=Miklós Ajtai|contribution=Oblivious RAMs without cryptographic assumptions [extended abstract]|doi=10.1145/1806689.1806716|mr=2743267|pages=181–190|publisher=Association for Computing Machinery|title=Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010)|year=2010|s2cid=260228 }}</ref><ref name="DMN11">{{citation |last1=Damgård |first1=Ivan |title=Theory of Cryptography - 8th Theory of Cryptography Conference, TCC 2011, Providence, RI, USA, March 28-30, 2011, Proceedings |volume=6597 |pages=144–163 |year=2011 |editor-last=Ishai |editor-first=Yuval |series=Lecture Notes in Computer Science |contribution=Perfectly secure oblivious RAM without random oracles |publisher=Springer |doi=10.1007/978-3-642-19571-6_10 |last2=Meldgaard |first2=Sigurd |last3=Nielsen |first3=Jesper Buus |author-link=Ivan Damgård |doi-access=free|isbn=978-3-642-19570-9 }}</ref> were aimed at removing this assumption completely. The authors of<ref name = "DMN11" /> also achieve an access overhead of <math>O(\log^3 n)</math>
While most of the earlier works focus on proving security computationally, there are more recent works<ref name = "CP13"/><ref name ="SCSL11" /><ref name ="A10" /><ref name ="DMN11" /> 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.<ref name ="GO96" /> They show a <math>\Omega(\log{n})</math> lower bound for ORAM access overhead, where <math>n</math> is the data size. Another lower bound is by Larsen and Nielsen.<ref name="LN18">{{citation|last1=Larsen|first1=Kasper Green|last2= Nielsen |first2=Jesper Buus|contribution=Yes, There is an Oblivious {RAM} Lower Bound!|doi=10.1007/978-3-319-96881-0_18|pages=523–542|publisher= Springer|title=Advances in Cryptology - CRYPTO|year=2018 }}</ref> There is also a conditional lower bound on the access overhead of ORAMs due to Boyle et al.<ref name ="BN16">{{citation|last1=Boyle|first1=Elette|author1-link=Elette Boyle|last2=Naor|first2=Moni|author2-link=Moni Naor|contribution=Is there an oblivious RAM lower bound?|doi=10.1145/2840728.2840761|mr=3629839|pages=357–368|publisher=Association for Computing Machinery|title=Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (ITCS '16)|year=2016|isbn=978-1-4503-4057-1 |s2cid=9729386 }}</ref> that relates this quantity with that of the size of sorting networks.
==ORAM constructions==
===Trivial construction===
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>\Omega(n)</math> for each memory operation, where {{mvar|n}} is the size of the memory.
===A simple ORAM scheme===
A simple version of a statistically secure ORAM compiler constructed by Chung and Pass<ref name = "CP13"/> is described in the following along with an overview of a proof of its correctness. The compiler on input {{mvar|n}} and a program {{math|Π}} with its memory requirement {{mvar|n}}, outputs an equivalent oblivious program {{math|Π′}}.
If the input program {{math|Π}} uses {{mvar|r}} registers, the output program {{math|Π′}} will need <math>r+n/{\alpha}+\text{poly}\log{n}</math> registers, where <math>\alpha>1</math> is a parameter of the construction. {{math|Π′}} uses <math>O(n \text{ poly} \log n)</math> memory and its (worst-case) access overhead is <math>O(\text{poly}\log n)</math>.
The ORAM compiler is very simple to describe. Suppose that the original program {{math|Π}} has instructions for basic mathematical and control operations in addition to two special instructions <math>\mathsf{read}(l)</math> and <math>\mathsf{write}(l,v)</math>, where <math>\mathsf{read}(l)</math> reads the value at location {{mvar|l}} and <math>\mathsf{write}(l,v)</math> writes the value {{mvar|v}} to {{mvar|l}}. The ORAM compiler, when constructing {{math|Π′}}, simply replaces each {{sans-serif|read}} and {{sans-serif|write}} instructions with subroutines {{sans-serif|Oread}} and {{sans-serif|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.
thumb|The ORAM compiler substitutes the read and write instructions in the original program with subroutines Oread and Owrite.
====Memory organization of the oblivious program====
The program {{math|Π′}} stores a complete binary tree {{mvar|T}} of depth <math>d=\log (n/\alpha)</math> in its memory. Each node in {{mvar|T}} is represented by a binary string of length at most {{mvar|d}}. The root is the empty string, denoted by {{mvar|λ}}. The left and right children of a node represented by the string <math>\gamma</math> are <math>\gamma_0</math> and <math>\gamma_1</math> respectively. The program {{math|Π′}} thinks of the memory of {{math|Π}} as being partitioned into blocks, where each block is a contiguous sequence of memory cells of size {{mvar|α}}. Thus, there are at most <math>\lceil n /\alpha \rceil</math> blocks in total. In other words, the memory cell {{mvar|r}} corresponds to block <math>b=\lfloor r/\alpha \rfloor</math>.
thumb|An illustration of the memory of the oblivious program showing the binary tree and position map.
At any point in time, there is an association between the blocks and the leaves in {{mvar|T}}. To keep track of this association, {{math|Π′}} also stores a data structure called a position map, denoted by <math>Pos</math>, using <math>O(n/\alpha)</math> registers. This data structure, for each block {{mvar|b}}, stores the leaf of {{mvar|T}} associated with {{mvar|b}} in <math>Pos(b)</math>.
Each node in {{mvar|T}} contains an array with at most {{mvar|K}} triples. Each triple is of the form <math>(b,Pos(b),v)</math>, where {{mvar|b}} is a block identifier and {{mvar|v}} is the contents of the block. Here, {{mvar|K}} is a security parameter and is <math>O(\text{poly} \log n)</math>.
====Description of the oblivious program====
The program {{math|Π′}} starts by initializing its memory as well as registers to {{math|⊥}}. Describing the procedures, {{sans-serif|Owrite}} and {{sans-serif|Oread}} is enough to complete the description of {{math|Π′}}. The sub-routine {{sans-serif|Owrite}} is given below. The inputs to the sub-routine are a memory location <math>l \in [n]</math> and the value {{mvar|v}} to be stored at the location {{mvar|l}}. It has three main phases, namely FETCH, PUT_BACK, and FLUSH.
'''input:''' a location {{mvar|l}}, a value {{mvar|v}}
'''Procedure FETCH''' // <u>Search for the required block.</u> <math>b\leftarrow \lfloor l/ \alpha \rfloor</math> // <u>{{mvar|b}} is the block containing {{mvar|l}}.</u> <math>i\leftarrow l\mod \alpha</math> // <u>{{mvar|i}} is {{mvar|l}}'s component in block {{mvar|b}}.</u> <math>pos\leftarrow Pos(b)</math> '''if''' <math>pos =\perp</math> '''then''' <math>pos\leftarrow_R [n/ \alpha]</math>. // <u>Set {{mvar|pos}} to a uniformly random leaf in {{mvar|T}}.</u> flag <math>\leftarrow 0</math>. '''for''' each node {{mvar|N}} on the path from the root to {{mvar|pos}} '''do''' '''if''' {{mvar|N}} has a triple of the form <math>(b,pos,x)</math> '''then''' Remove <math>(b,pos,x)</math> from {{mvar|N}}, store {{mvar|x}} in a register, and write back the updated {{mvar|N}} to {{mvar|T}}. flag <math>\leftarrow 1</math>. '''else''' Write back {{mvar|N}} to {{mvar|T}}.
'''Procedure PUT_BACK''' // <u>Add back the updated block at the root.</u> <math>pos'\leftarrow_R [n/ \alpha]</math>. // <u>Set {{mvar|pos'}} to a uniformly random leaf in {{mvar|T}}.</u> '''if''' flag<math>=1</math> '''then''' Set {{mvar|x'}} to be the same as {{mvar|x}} except for {{mvar|v}} at the {{mvar|i}}-th position. '''else''' Set {{mvar|x'}} to be a block with {{mvar|v}} at {{mvar|i}}-th position and {{math|⊥}}'s everywhere else. '''if''' there is space left in the root '''then''' Add the triple <math>(b,pos',x')</math> to the root of {{mvar|T}}. '''else''' Abort outputting '''overflow'''.
'''Procedure FLUSH''' // <u>Push the blocks present in a random path as far down as possible.</u> <math>pos^*\leftarrow_R [n/ \alpha]</math>. // <u>Set <math>pos^*</math> to a uniformly random leaf in {{mvar|T}}.</u> '''for''' each triple <math>(b'',pos'',v'')</math> in the nodes traversed the path from the root to <math>pos^*</math> Push down this triple to the node {{mvar|N}} that corresponds to the longest common prefix of <math>pos''</math> and <math>pos^*</math>. '''if''' at any point some bucket is about to overflow '''then''' Abort outputting '''overflow'''.
The task of the FETCH phase is to look for the location {{mvar|l}} in the tree {{mvar|T}}. Suppose {{mvar|pos}} is the leaf associated with the block containing location {{mvar|l}}. For each node {{mvar|N}} in {{mvar|T}} on the path from root to {{mvar|pos}}, this procedure goes over all triples in {{mvar|N}} and looks for the triple corresponding to the block containing {{mvar|l}}. If it finds that triple in {{mvar|N}}, it removes the triple from {{mvar|N}} and writes back the updated state of {{mvar|N}}. Otherwise, it simply writes back the whole node {{mvar|N}}.
In the next phase, it updates the block containing {{mvar|l}} with the new value {{mvar|v}}, associates that block with a freshly sampled uniformly random leaf of the tree, and writes back the updated triple to the root of {{mvar|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>pos^*</math> and then tries to push down every node as much as possible along the path from root to <math>pos^*</math>. It aborts outputting an overflow if at any point some bucket is about to overflow its capacity.
The sub-routine {{sans-serif|Oread}} is similar to {{sans-serif|Owrite}}. For the {{sans-serif|Oread}} sub-routine, the input is just a memory location <math>l \in [n]</math> and it is almost the same as {{sans-serif|Owrite}}. In the FETCH stage, if it does not find a triple corresponding to location {{mvar|l}}, it returns {{math|⊥}} as the value at location {{mvar|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.
====Correctness of the simple ORAM scheme====
Let {{mvar|C}} stand for the ORAM compiler that was described above. Given a program {{math|Π}}, let {{math|Π′}} denote <math>C(\Pi)</math>. Let <math>\Pi(n,x)</math> denote the execution of the program {{math|Π}} on an input {{mvar|x}} using {{mvar|n}} memory cells. Also, let <math>\tilde{\Pi}(n,x)</math> denote the memory access pattern of <math>\Pi(n,x)</math>. Let {{mvar|μ}} denote a function such that for any <math>n \in \mathbb{N}</math>, for any program {{math|Π}} and for any input <math>x \in \{0,1\}^*</math>, the probability that <math>\Pi'(n,x)</math> outputs an overflow is at most <math>\mu(n)</math>. The following lemma is easy to see from the description of {{mvar|C}}.
;Equivalence Lemma: Let <math>n \in \mathbb{N}</math> and <math>x \in \{0,1\}^*</math>. Given a program {{math|Π}}, with probability at least <math>1 - \mu(n)</math>, the output of <math>\Pi'(n,x)</math> is identical to the output of <math>\Pi(n,x)</math>.
It is easy to see that each {{sans-serif|Owrite}} and {{sans-serif|Oread}} operation traverses root-to-leaf paths in {{mvar|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 {{tmath|\Pi_1}} and {{tmath|\Pi_2}} and two inputs <math>x_1,x_2 \in \{0,1\}^*</math> such that <math>|\tilde{\Pi_1}(x_1,n)| = |\tilde{\Pi_2}(x_2,n)|</math>, with probability at least <math>1 - 2\mu(n)</math>, the access patterns <math>\tilde{\Pi_1'}(x_1,n)</math> and <math>\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 {{mvar|μ}} such that for every program {{math|Π}}, every {{mvar|n}} and input {{mvar|x}}, the program <math>\Pi'(n,x)</math> outputs overflow with probability at most <math>\mu(n)</math>.
====Computational and memory overheads====
During each {{sans-serif|Oread}} and {{sans-serif|Owrite}} operation, two random root-to-leaf paths of {{mvar|T}} are fully explored by {{math|Π′}}. This takes <math>O(K\cdot\log (n/\alpha))</math> time. This is the same as the computational overhead and is <math>O(\text{poly}\log n)</math> since {{mvar|K}} is <math>O(\text{poly}\log n)</math>.
The total memory used up by {{math|Π′}} is equal to the size of {{mvar|T}}. Each triple stored in the tree has <math>\alpha + 2</math> words in it and thus there are <math>K(\alpha + 2)</math> words per node of the tree. Since the total number of nodes in the tree is <math>O(n/\alpha)</math>, the total memory size is <math>O(nK)</math> words, which is <math>O(n\text{ poly}\log n)</math>. Hence, the memory overhead of the construction is <math>O(\text{poly}\log n)</math>.
<!-- ==Definition== Suppose RAM: <math>[1, 2, 3, ..., n]</math>;
Sequence: S= <math>[OP_1, OP_2, OP_3, ..., OP_m]</math> where each <math>OP_i</math> is read [address] or write [address, data] operation;
There are various sequences of operations that result in the same configuration of RAM. We want an algorithm that, given sequence S, produces another sequence S’ that performs the same task in a RAM-Oblivious way. In other words, the access pattern of S' is independent of S. Thus, the RAM is Oblivious RAM.
The definition of a memory oblivious algorithm is as follows: “A program P is ‘memory oblivious’ if the memory access pattern is independent of input S”. Formally speaking, let Access Pattern AP(x) be the sequence of memory accesses for program P with input x.
P is memory oblivious means <math>\forall x,y ((x\neq y)\land(\left\vert x \right\vert = \left\vert y \right\vert)) \Longrightarrow AP(x) \approx AP(y)</math>
This definition of memory oblivious helps us state the definition of Oblivious RAM problem as: Given a program P, what is the most efficient program Q=P such that Q is memory oblivious. In this case, once the inputs are same, we can get identical outputs.
==Formal definition== We begin by defining the access pattern at the sequence of memory locations which the CPU accesses during computation. This definition applies also to an oracle-CPU (The CPU interaction with MEMORY is a sequence of triples <math>(i, a, v)</math> of “instruction”, “address” and “values” respectively).
Definition of Access Pattern: The access pattern, denoted <math>\mathcal{A}^k(y)</math>, of a deterministic <math>RAM_k</math> on input {{mvar|y}} is a sequence <math>(a_1,...,a_i,...)</math>, such that for every {{mvar|i}}, the <math>i-th</math> message sent by <math>CPU_k</math>, when interacting with <math>MEM_k(y)</math>, is of the form<math>(.,a_i,.)</math>. Similarly, we can define the access pattern of an <math>oracle-RAM_k</math> on a specific input {{mvar|y}} and access to a specific function {{mvar|f}}.
Considering the probabilistic-RAMs, we define a random variable which for every possible function {{mvar|f}} assigns the access pattern which corresponds to computations in which the RAM has access to this function.
Definition of Access Pattern of a Probabilistic-RAM: The access pattern, denoted <math>{\mathcal\bar{A}^k(y)}</math>, of a probabilistic-<math>RAM_k</math> on input {{mvar|y}} is a random variable which assumes the value of the access pattern of <math>RAM_k</math> on a specific input {{mvar|y}} and access to a uniformly selected function {{mvar|f}}.
Now, we are ready to define an <math>Oblivious RAM</math>. We define an <math>Oblivious RAM</math> to be a probabilistic <math>RAM</math> for which the probability distribution of the sequence of memory addresses accessed during an execution depends only on the running time(i.e., is independent of particular input).
Formal definition of <math>Oblivious RAM</math>: For every <math>k\in N</math>, we define an oblivious <math>RAM_k</math> as a probabilistic-<math>RAM_k</math> satisfying the following condition. For every two strings, <math>y_1</math> and <math>y_2</math>, if <math>\left\vert {\mathcal\bar{A}^k(y_1)} \right\vert</math> and <math>\left\vert {\mathcal\bar{A}^k(y_2)} \right\vert</math> are identically distributed then so are <math>{\mathcal\bar{A}^k(y_1)}</math> and <math>{\mathcal\bar{A}^k(y_2)}</math>. Intuitively, the sequence of memory accesses of an oblivious <math>RAM_k</math> reveals no information about the input( to the <math>RAM_k</math>), beyond the running-time for the input.
===Oblivious simulation=== Now that we have define both <math>RAM</math> and <math>Oblivious RAM</math>, it is left only specify what is meant by an <math>Oblivious</math> <math>Simulation</math>of an arbitrary <math>RAM</math> program on an <math>Oblivious RAM</math>, our notion of simulation is minimal one: it only requires that both machines compute the same function. The <math>RAM</math> simulation presented in the sequel are simulations in a much stronger sense: specifically, they are “on-line”. On the other hand, an oblivious simulation of a <math>RAM</math> is not merely a simulation by an oblivious RAM. In addition, we require that inputs having identical running-time on the original <math>RAM</math>, maintain identical running-time on the Oblivious <math>RAM</math>, so that the obliviously condition applies to them in a non-vacuous manner. For the sake of simplicity, we present only definition for oblivious simulation of deterministic RAMs.
Definition of <math>Oblivious</math> <math>Simulation</math> of <math>RAM</math>: Given <math>probabilistic-RAM'_{k'}</math>, and <math>RAM_k</math>, we say that a <math>probabilistic-RAM'_{k'}</math>, obliviously simulates <math>RAM_k</math> if the following conditions hold.
1. The <math>probabilistic-RAM'_{k'}</math> simulates <math>RAM_k</math> with probability 1. In other words, for every input y, and every choice of an oracle function {{mvar|f}}, the output of <math>oracle-RAM'_{k'}</math>, on input {{mvar|y}} and access to oracle {{mvar|f}}, equals the output of <math>RAM_k</math> on input {{mvar|y}}.
2. The <math>probabilistic-RAM'_{k'}</math> is oblivious. (We stress that we refer here to the access pattern of <math>RAM'_{K'}</math> on a fixed input and a randomly chosen oracle function.)
3. The random variable representing the running-time of <math>probabilistic-RAM'_{k'}</math> is fully specifies by the running-time <math>RAM_k</math> (on input {{mvar|y}}).(Here again we refer to the behavior of <math>RAM'_{K'}</math> on fixed input and a randomly chosen oracle function.)
Hence, the access pattern in an oblivious simulation (which is a random variable defined over the choice of the random oracle) has a distribution depending only on the running-time of the original machine. Namely, let <math>{\mathcal\bar{A}^k(y)}</math> denote the access pattern in an oblivious simulation of the computation of <math>RAM_k</math> on input {{mvar|y}}. Then, <math>{\mathcal\bar{A}^k(y_1)}</math> and <math>{\mathcal\bar{A}^k(y_2)}</math> are identically distributed if the running-time of <math>RAM_k</math> on these inputs (i,e., <math>y_1</math> and <math>y_2</math>) is identical.
We note that in order to define oblivious simulations of <math>oracle-RAMs</math>, we have to supply the simulating <math>RAM</math> with two oracles (i.e., one identical to the oracle of the simulated machine and the other being a random oracle). Besides, these two oracles can be incorporated into one, but in any case the formulation will be slightly more cumbersome.
We need to define the overhead of oblivious simulation.
Definition of Overhead of Oblivious Simulations:
Given <math>probabilistic-RAM'_{k'}</math>, <math>RAM_k</math>, and suppose that a <math>probabilistic-RAM'_{k'}</math>, obliviously simulates the computation of <math>RAM_k</math>, and let y: <math>g: \Bbbk\mapsto\Bbbk</math> be a function. We say that the overhead of the simulation is at most {{mvar|g}} if, for every {{mvar|y}}, the expected running-time of <math>RAM'_{K'}</math> on input {{mvar|y}} is bounded above by <math>g(T)\cdot T</math>, where {{mvar|T}} denoted the running-time of <math>RAM_k</math> on input {{mvar|y}}.
===Solution===
====Computer model construction==== * Two parts: Memory and Processors * Internal memory of process: <math>c\log\left\vert Memory \right\vert</math> * Interaction: <math>fetch(address)</math>, <math>store(address, value)</math> * Processor has access to random oracle * Computation starts with a program and an input in <math>Memory</math> * One step: fetch one cell - update value and Processor memory - store
====Oblivious execution==== We want to hide orders of access to cells of <math>Memory</math>, thus we define Oblivious Execution as for all programs of size {{mvar|m}} working in time {{mvar|t}}, an order of fetch/store address is the same. The weaker requirement is for all programs of size {{mvar|m}} working in time {{mvar|t}}, order of fetch/store address has the same distribution.
====Basic solution====
=====Naive simulation===== # We store encrypted pairs(address, value) in memory cells # For every fetch/store we scan through all memory. If the address is wrong, re-encrypt and store the data, otherwise, do the job which means encrypt and store the results. Cost of simulation: <math>tm</math> time, {{mvar|m}} memory
=====Square root solution===== We need to protect order of accesses and number of accesses. Because <math>Memory = Main Part (m + \sqrt{m}) \mid Shelter \sqrt{m}</math>, the idea comes that: firstly we divide computation in epochs of <math>\sqrt{m}</math> steps each. Then on each original step, we make one fetch to the <math>Main Part</math> and scan through all the <math>Shelter</math>.
Square Root simulation # Store input in the <math>Main Part</math> # Add <math>\sqrt{m}</math> dummy cells to the <math>Main Part</math> # for every epoch of <math>\sqrt{m}</math> steps ## Permute all cells in the <math>Main Part</math>(using permutation {{math|Π}} from random oracle) ## For each process({{mvar|i}}) scan through the <math>Shelter</math>. If <math>i-th</math> element is not founded, fetch it from <math>\pi(i)</math>, otherwise fetch next dummy cell ## Update(Obliviously) the <math>Main Part</math> using the <math>Shelter</math> values Cost of simulation: <math>t\sqrt{m}</math> time, <math>m + 2\sqrt{m}</math> memory
=====Buffer solution===== Buffer solution refers to Oblivious Hash Table. Suppose we have a memory of initial program: <math>(a_1, v_1), ..., (a_m, v_m)</math> # Take a hash function h : <math>[1...m]\rightarrow[1...m]</math> # Prepare <math>m \times \log m</math> table # Put <math>(a_i, v_i)</math> to a random free call in <math>h(a_i)-th</math> column # The chance of overflow is less than <math>1/m</math> Simulation: # Construct (obliviously) a hash table # For every step <math>fetch(i)</math> of initial program ## Scan through <math>h(i)</math> column ## Update the target cell Cost of simulation : <math>t \log m</math> time, <math>m \log m</math> memory
====Hierarchical construction==== Data structure : Oblivious Data Structure * <math>k-buffer</math> = table <math>2^k \times k</math> * Hierarchical Buffer Structure = <math>1-buffer, ..., \log t-buffer</math> * Initial position : input in last buffer, all others are empty
=====Hierarchical simulation===== Simulation of processing cell {{mvar|i}}: # Scan through <math>1-buffer</math> # For every j scan through <math>h(i,j)</math>-th column in <math>j-buffer</math> # Put the updated value to the first buffer
=====Periodic rehashing===== Refreshing the data structure: # Every <math>2^{j-1}</math> steps unify {{mvar|j}}-th and <math>j-1</math>-th buffer # Delete doubles # Using new hash function put all data to <math>j-th</math> level Invariant: For every moment of time for every {{mvar|I}} buffers from 1 to {{mvar|I}} all together contain at most <math>2^{I-1}</math> elements.
Cost of simulation: <math>O(t \cdot (\log t)^3)</math> time, <math>O(m \cdot (\log m)^2)</math> memory
Omitted details: realization of oblivious hashing and random oracle
===Sorting network=== When allowing for parallel comparators, we can trivially sort an array in O(n) time. But there are much better sorting networks. Optimally, there is a way to getting O(n logn) comparisons in O(logn) parallel time.<ref>{{Cite conference | doi = 10.1145/800061.808726| title = An {{math|''O''(''n'' log ''n'')}} sorting network| work = Proceedings of the fifteenth annual ACM symposium on Theory of computing | conference = STOC '83| pages = 1–9| year = 1983| last1 = Ajtai | first1 = M. |author-link1 = Miklós Ajtai| last2 = Komlós | first2 = J. |author-link2 = János Komlós (mathematician)| last3 = Szemerédi | first3 = E. |author-link3 = Endre Szemerédi| isbn = 0-89791-099-0}}</ref> -->
==References== {{reflist}}
==See also== * Oblivious data structure * Cache-oblivious algorithm
Category:Models of computation Category:Cache (computing) Category:Analysis of algorithms