This article has multiple issues. Please help improve it or discuss these issues on the talk page . (Learn how and when to remove these template messages)
|
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. [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 can be made oblivious and that the running time of the oblivious TM is . 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 denote a program requiring memory of size when executing on an input . Suppose that has instructions for basic mathematical and control operations in addition to two special instructions and , where reads the value at location and writes the value to . The sequence of memory cells accessed by a program during its execution is called its memory access pattern and is denoted by .
A polynomial-time algorithm is an Oblivious RAM (ORAM) compiler with computational overhead and memory overhead , if given and a deterministic RAM program with memory-size outputs a program with memory-size such that for any input , the running-time of is bounded by where is the running-time of , and there exists a negligible function such that the following properties hold:
Note that the above definition uses the notion of statistical security. One can also have a similar definition for the notion of computational 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 server space and incurs a running time overhead of when making a program that uses 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. [6] , called "OptORAMa", is the first optimal ORAM construction. It achieves client storage, server storage, and 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 worst-case access overheads. 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. 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 [13] [14] were aimed at removing this assumption completely. The authors of [14] also achieve an access overhead of
While most of the earlier works focus on proving security computationally, there are more recent works [3] [10] [13] [14] 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. [1] They show a lower bound for ORAM access overhead, where is the data size. Another lower bound is by Larsen and Nielsen. [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. This scheme incurs a time overhead of 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 [3] is described in the following along with an overview of a 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 registers, where is a parameter of the construction. Π′ uses memory and its (worst-case) access overhead is .
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 and , where reads the value at location l and 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 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 are and 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 blocks in total. In other words, the memory cell r corresponds to block .
At any point in 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 a position map, denoted by , using registers. This data structure, for each block b, stores the leaf of T associated with b in .
Each node in T contains an array with at most K triples. Each triple is of the form , where b is a block identifier and v is the contents of the block. Here, K is a security parameter and is .
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 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. // b is the block containing l. // i is l's component in block b.ifthen. // Set pos to a uniformly random leaf in T. flag . for each node N on the path from the root to posdoifN has a triple of the form then Remove from N, store x in a register, and write back the updated N to T. flag . else Write back N to T.
Procedure PUT_BACK // Add back the updated block at the root.. // Set pos' to a uniformly random leaf in T.if flagthen Set x' to be the same as x except for v at the i-th position. else Set x' to be a block with v at i-th position and ⊥'s everywhere else. if there is space left in the root then Add the triple to the root of T. else Abort outputting overflow.
Procedure FLUSH // Push the blocks present in a random path as far down as possible.. // Set to a uniformly random leaf in T.for each triple in the nodes traversed the path from the root to Push down this triple to the node N that corresponds to the longest common prefix of and . 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 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 and then tries to push down every node as much as possible along the path from root to . 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 and it is almost the same as Owrite. 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.
Let C stand for the ORAM compiler that was described above. Given a program Π, let Π′ denote . Let denote the execution of the program Π on an input x using n memory cells. Also, let denote the memory access pattern of . Let μ denote a function such that for any , for any program Π and for any input , the probability that outputs an overflow is at most . The following lemma is easy to see from the description of C.
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.
The following lemma completes the proof of correctness of the ORAM scheme.
During each Oread and Owrite operation, two random root-to-leaf paths of T are fully explored by Π′. This takes time. This is the same as the computational overhead and is since K is .
The total memory used up by Π′ is equal to the size of T. Each triple stored in the tree has words in it and thus there are words per node of the tree. Since the total number of nodes in the tree is , the total memory size is words, which is . Hence, the memory overhead of the construction is .
In computational complexity theory, bounded-error quantum polynomial time (BQP) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances. It is the quantum analogue to the complexity class BPP.
In probability theory and statistics, the Gumbel distribution is used to model the distribution of the maximum of a number of samples of various distributions.
In mathematics, a foliation is an equivalence relation on an n-manifold, the equivalence classes being connected, injectively immersed submanifolds, all of the same dimension p, modeled on the decomposition of the real coordinate space Rn into the cosets x + Rp of the standardly embedded subspace Rp. The equivalence classes are called the leaves of the foliation. If the manifold and/or the submanifolds are required to have a piecewise-linear, differentiable, or analytic structure then one defines piecewise-linear, differentiable, or analytic foliations, respectively. In the most important case of differentiable foliation of class Cr it is usually understood that r ≥ 1. The number p is called the dimension of the foliation and q = n − p is called its codimension.
In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". The two most commonly analyzed resources are time and memory.
In computational complexity theory, PostBQP is a complexity class consisting of all of the computational problems solvable in polynomial time on a quantum Turing machine with postselection and bounded error.
Automatically Tuned Linear Algebra Software (ATLAS) is a software library for linear algebra. It provides a mature open source implementation of BLAS APIs for C and FORTRAN 77.
In coding theory and information theory, a Z-channel or binary asymmetric channel is a communications channel used to model the behaviour of some data storage systems.
In probability theory and statistics, a categorical distribution is a discrete probability distribution that describes the possible results of a random variable that can take on one of K possible categories, with the probability of each category separately specified. There is no innate underlying ordering of these outcomes, but numerical labels are often attached for convenience in describing the distribution,. The K-dimensional categorical distribution is the most general distribution over a K-way event; any other discrete distribution over a size-K sample space is a special case. The parameters specifying the probabilities of each possible outcome are constrained only by the fact that each must be in the range 0 to 1, and all must sum to 1.
The exponential mechanism is a technique for designing differentially private algorithms. It was developed by Frank McSherry and Kunal Talwar in 2007. Their work was recognized as a co-winner of the 2009 PET Award for Outstanding Research in Privacy Enhancing Technologies.
In cryptography, learning with errors (LWE) is a mathematical problem that is widely used to create secure encryption algorithms. It is based on the idea of representing secret information as a set of equations with errors. In other words, LWE is a way to hide the value of a secret by introducing noise to it. In more technical terms, it refers to the computational problem of inferring a linear -ary function over a finite ring from given samples some of which may be erroneous. The LWE problem is conjectured to be hard to solve, and thus to be useful in cryptography.
In discrete mathematics, ideal lattices are a special class of lattices and a generalization of cyclic lattices. Ideal lattices naturally occur in many parts of number theory, but also in other areas. In particular, they have a significant place in cryptography. Micciancio defined a generalization of cyclic lattices as ideal lattices. They can be used in cryptosystems to decrease by a square root the number of parameters necessary to describe a lattice, making them more efficient. Ideal lattices are a new concept, but similar lattice classes have been used for a long time. For example, cyclic lattices, a special case of ideal lattices, are used in NTRUEncrypt and NTRUSign.
In differential geometry, the integration along fibers of a k-form yields a -form where m is the dimension of the fiber, via "integration". It is also called the fiber integration.
In coding theory, Zemor's algorithm, designed and developed by Gilles Zemor, is a recursive low-complexity approach to code construction. It is an improvement over the algorithm of Sipser and Spielman.
In functional analysis, a Markushevich basis is a biorthogonal system that is both complete and total.
IQ imbalance is a performance-limiting issue in the design of a class of radio receivers known as direct conversion receivers. These translate the received radio frequency signal directly from the carrier frequency to baseband using a single mixing stage.
Beamforming is a signal processing technique used to spatially select propagating waves. In order to implement beamforming on digital hardware the received signals need to be discretized. This introduces quantization error, perturbing the array pattern. For this reason, the sample rate must be generally much greater than the Nyquist rate.
In computer science, an oblivious data structure is a data structure that gives no information about the sequence or pattern of the operations that have been applied except for the final result of the operations.
In computational statistics, the Metropolis-adjusted Langevin algorithm (MALA) or Langevin Monte Carlo (LMC) is a Markov chain Monte Carlo (MCMC) method for obtaining random samples – sequences of random observations – from a probability distribution for which direct sampling is difficult. As the name suggests, MALA uses a combination of two mechanisms to generate the states of a random walk that has the target probability distribution as an invariant measure:
Quantum counting algorithm is a quantum algorithm for efficiently counting the number of solutions for a given search problem. The algorithm is based on the quantum phase estimation algorithm and on Grover's search algorithm.
In computer science, the list-labeling problem involves maintaining a totally ordered set S supporting the following operations: