Gradual GRAM and secure computation for RAM programs 1

1. Introduction

Background. Secure multi-party computation (MPC) protocols allow a group of parties to compute some function f on the parties’ private inputs, while preserving a number of security properties such as privacy and correctness. This area has witnessed a tremendous progress in the past two decades both in the two-party setting [4,20,21,25,29,30,37,41,42,46,47,53], and with a larger number of parties [7,9,23,31,48]. Nevertheless, most of this research has been conducted for Boolean circuits and falls short when the computation involves accesses to a large memory, which are translated into a linear scan of the memory inside the circuit. This translation is required for every memory access and causes a huge blowup in the description of the circuit. Moreover, the majority of applications encountered in practice today are more efficiently captured using random-access memory (RAM) programs that allow constant-time memory lookup and contain branches, recursions and loops. This covers graph algorithms such as the known Dijkstra’s shortest path algorithm, binary search on sorted data, finding the kth-ranked element, the Gale-Shapely stable matching algorithm and many more. Generic transformations from RAM programs that run in time T imply circuits of size O ( T 3 log T ) which are non-scalable even for relatively small memory sizes [6,39].

To address these limitations secure protocols have been designed directly in the RAM model, either with round complexity that grows with the running-time of the RAM program [8,10,19,27,28] or with constant round complexity [1,10–15,24,32–34,49]. A fundamental tool in designing protocols in the RAM model is Oblivious RAM (ORAM) [16,17,38], which supports dynamic memory access with polylogarithmic cost while preventing any leakage from the memory. Namely, ORAM is a technique for hiding all the information about the memory of a RAM program, including both the content of the memory and the access pattern to it. The efficiency of ORAM constructions is evaluated by their bandwidth and storage blowups where the former refers to the number of data blocks that are sent between the parties per memory access and the later refers to the multiplicative overhead of the oblivious memory size. Recent constructions incur practical polylogarithmic overheads in the size of memory [5,44,45].

Basic notations. We denote the security parameter by κ. We say that a function μ : N → N is negligible if for every positive polynomial p ( · ) and all sufficiently large κ’s it holds that μ ( κ ) < 1 p ( κ ) . We use the abbreviation PPT to denote probabilistic polynomial-time and denote by [ n ] the set of elements { 1 , … , n } for some n ∈ N .

We specify next the definition of computationally indistinguishability.

Definition 2.1.

Let X = { X ( a , κ ) } a ∈ { 0 , 1 } ∗ , κ ∈ N and Y = { Y ( a , κ ) } a ∈ { 0 , 1 } ∗ , κ ∈ N be two distribution ensembles. We say that X and Y are computationally indistinguishable, denoted X ≈ c Y , if for every PPT machine D , there exists a negligible function negl such that: | Pr [ D ( X ( a , κ ) , 1 κ ) = 1 ] − Pr [ D ( Y ( a , κ ) , 1 κ ) = 1 ] | ⩽ negl ( κ ) .

2.1. Pseudorandom functions

2.3. The RAM model of computation

We start with the notation of computation in the RAM model. Given a program P, with access to memory D of size n, that obtains a “short” input x which we alternatively think of as the initial state of the program. We use the notation P D ( x ) to denote the execution of program P with initial memory contents D and input x. The program can read/write to various locations in memory D throughout its execution. We also consider the case where several different programs are executed sequentially and the memory persists between executions. Specifically, this process is denoted by ( y 1 , … , y c ) = ( P 1 ( x 1 ) , … , P c ( x c ) ) D to indicate that P 1 D ( x 1 ) is executed first, resulting in some memory contents D 1 and an output y 1 , following that P 2 D 1 ( x 2 ) is executed resulting in some memory contents D 2 and an output y 2 and so on.

CPU-step circuit. We consider a RAM program as a sequence of at most T small CPU-steps, where each of them is represented by a circuit that computes the following functionality: C CPU P ( state t , v t read ) = ( state t + 1 , i t + 1 read , v t + 1 write ) , 1 ⩽ t ⩽ T Namely, this circuit takes as input the CPU state state t and a value v t read that was read from the last read memory location, and outputs an updated state state t + 1 , the next location to read i t + 1 read and a value v t + 1 write to write into that location. Note that this description simplifies the standard definition of a computation in the RAM model, where the program must write to the same location that it just read from. The computation P D ( x ) starts with the initial state set as state 1 = x and in each step t the memory D is updated according to the output of the C CPU P ( state t , v t read ) . The access pattern of the computation P D ( x ) is the sequence of locations and read/write values that were observed during the computation, namely MemAccess ( P , n , x ) = { i t read , v t write } t ∈ [ T ] . In addition, the number of memory accesses that were performed during a program execution is denoted by T ( P , n , x ) (that is, the running time of the program P with memory of size n on input x).

2.4. Oblivious RAM (ORAM)

In a sequence of seminal works [16,17,38], Goldreich and Ostrovsky introduced the notion of Oblivious RAM (ORAM) which is a mechanism that simulates read/write access to an underlying memory D via a sequence of accesses to a compiler memory D ′ . The complied memory ensures that no information about both the content of the memory D as well as the access pattern to it are leaked by observing the memory D ′ and the complied access pattern. In the client-server model, ORAM allows the client to store its private database on the server and obliviously process it by only maintaining a relatively small local memory. The efficiency of ORAM constructions is evaluated by their bandwidth blowup, client’s storage and server’s storage. Bandwidth blowup is the number of data blocks that must to be sent between the parties per request. Client’s storage is the amount of trusted local memory required for the client to manage the ORAM whereas server’s storage is the amount of storage needed to store the data blocks. In [17], Goldreich and Ostrovsky presented a probabilistic oblivious RAM with a polylogarithmic slowdown in the running time and further showed a logarithmic lower bound on the running time slowdown. Since their seminal work, ORAM has been extensively studied [18,40,43,44,51], optimizing different metrics and parameters. We continue with the notations of ORAM and secure ORAM.

Definition 2.4.

An oblivious RAM (ORAM) scheme consists of two algorithms ( OData , OProg ) as follows:

D ′ ← OData ( D , SK ) : Takes as input a memory D and a symmetric secret key SK and outputs an encoded memory D ′ .

P ′ ← OProg ( P ) : Takes as input a program P that is represented as a sequence of T CPU-steps and outputs a compiled program P ′ which works over D ′ and computes the same function as P D ( x ) .

A PPT algorithm C is an ORAM compiler with computational overhead c ( · ) and memory overhead m ( · ) , if C, when given n ∈ N and a deterministic RAM program P with memory size n, outputs a program P ′ with memory size m ( n ) · n , such that for any input x ∈ { 0 , 1 } ∗ , uniformly random key SK ∈ { 0 , 1 } κ (where κ is the security parameter) and uniformly random string r ∈ { 0 , 1 } κ , it follows that T ( P ′ ( n , x , SK , r ) ) = c ( n ) · T ( P , n , x ) and there exists a negligible function μ such that the following properties hold:

Correctness. For any n ∈ N , any input x ∈ { 0 , 1 } ∗ , any key and uniformly random string SK , r ∈ { 0 , 1 } κ , with probability at least 1 − μ ( κ ) , P ′ ( n , x , SK , r ) = P ( n , x ) .

Obliviousness. For any two programs P 1 , P 2 , any n ∈ N , any two inputs, uniformly random keys and uniformly random strings: x 1 , x 2 ∈ { 0 , 1 } ∗ , SK 1 , SK 2 , r 1 , r 2 ∈ { 0 , 1 } κ respectively, if T ( P 1 ( n , x 1 ) ) = T ( P 2 ( n , x 2 ) ) and P 1 ′ ← C ( n , P 1 , ρ 1 ) , P 2 ′ ← C ( n , P 2 , ρ 2 ) then the memory accesses MemAccess ( P 1 ′ ( n , x 1 , SK 1 , r 1 ) ) and MemAccess ( P 2 ′ ( n , x 2 , SK 2 , r 2 ) ) are computationally indistinguishable, where the random tapes ρ 1 , ρ 2 that were used by the compiler to generate the compiled programs are given to the distinguisher.

Note that the above definition (just as the definition from [17]) only requires an oblivious compilation of deterministic programs P. This is without loss of generality as we can always view a randomized program as a deterministic one that receives random coins as part of its input.

2.5. Tree-based ORAM constructions

The most common data-structure used in ORAM constructions is a binary tree where the data is associated with the tree leaves and updates operations are implemented by re-entering the new block. Namely, the server stores a binary tree of height L with 2 L leaves, where typically L = ⌈ log n ⌉ . The levels of the tree are enumerated from 0 (the root level) to L (the leaves level). Each tree node is associated with a bucket which may contain a constant number of entries defined as the capacity of the bucket. In order to avoid an overflow in a bucket, the data entries are pushed down the tree according to their associated paths via an eviction procedure. In this work we explore two known tree-based ORAM constructions: Simple ORAM and Circuit ORAM, and prove that they meet our gradual ORAM definition and their usefulness in designing GRAM (Section 2.7). Below we present the details of Simple ORAM and Circuit ORAM.

Simple ORAM [ 5 ]. We outline the ORAM construction of Chung et al. [5] which is based on the tree ORAM of [43] but with some crucial modifications that significantly simplify the analysis. We next present the two algorithms ( OData , OProg ) :

D ′ ← OData ( D , SK ) : The data D is organized into a binary tree of depth d = log n . Each node in the tree corresponds to a data bucket with capacity O ( log n ) . Each address from the original data is assigned to a random leaf node and is stored in some bucket on the path from the root to this random leaf. The leafmap (which stores the association of each address to the its leaf) is stored on the client but can be stored recursively in a tree ORAM. Each bucket stores (at most) O ( log n ) tuples ( i , pos , v ) where v is the content of the address i and pos is the leaf associated with that address. Furthermore, all data buckets are encrypted using an encryption scheme with a symmetric key SK , where every time a data bucket is written back it is encrypted again using fresh randomness.

P ′ ← OProg ( P ) : Given the complied program P that is comprised from a sequence virtual IO operation (either read from address i or write value v ′ to address i) do the following:

Read / Write : look up the leaf that is associated with the address i in the l e a f m a p and assign pos = l e a f m a p ( i ) . Next, traverse the tree from the root to the leaf pos and search for the tuple ( i , pos , v ) . More precisely, read each bucket on the path from the root to leaf pos . If the bucket contains the address i, remove it from that bucket, pick a uniformly random leaf pos ′ , set leafmap ( i ) = pos ′ and add the tuple ( i , pos ′ , v ′ ) to the root. Then, write that bucket back to the tree (without that tuple). Otherwise, if the bucket does not contain the address i, just write it back (unchanged). Finally return the value v. Eviction : Pick a uniformly random leaf pos ∗ and traverse the tree from the root to the leaf pos ∗ . For each bucket, ”push down” each tuple ( i ″ , pos ″ , v ″ ) as far as possible along the path to pos ∗ while ensuring that the tuple is still on the path to its associated leaf pos ″ (that is, the tuple ends up in the node γ = longest common prefix of pos ″ and pos ∗ .)

More formally, OProg takes as input a program P the is represented as a sequence of at most T small CPU-steps, where each step is represented by a circuit that computes the following functionality: C CPU P ( state t , v t read ) = ( state t + 1 , i t + 1 read , v t + 1 write ) , 1 ⩽ t ⩽ T

Then OProg outputs the complied program P ′ that is represented as a sequence of at most T ′ = 2 × log n × T CPU-steps. Each C CPU P ′ circuit takes as input a bucket B read and computes either the Read / Write or the Eviction procedures. In the Read / Write procedure the circuit searches for the tuple ( i read , pos , v ) in the bucket B read and outputs an updated bucket B write to be written in the same position. In the Eviction procedure the circuit checks whether each tuple in the bucket B read can be pushed down and outputs an updated bucket B write to be written in that position, and a temporary bucket B temp that should be written to the next bucket on the path. The C CPU P ′ circuit is described in Fig. 1. In order to simplify notation we omit the data encryption part from the description. However, note that for each write or read operation the data must be respectively encrypted and decrypted.

OPEN IN VIEWER

Fig. 1.

The description of C CPU P ′ circuit.

Circuit ORAM [ 45 ]. We next outline the ORAM construction of Wang et al. [45] which is also based on the tree ORAM of [43]. The Circuit ORAM improves the complexity of the eviction procedure and achieves almost optimal circuit size for realistic choices of block sizes. We next present the two algorithms ( OData , OProg ) :

D ′ ← OData ( D , SK ) : The data D is organized into a binary tree of depth d = log n . Each node in the tree corresponds to a data bucket with capacity Z = O ( 1 ) . As in the Simple ORAM construction, each block stores a tuple ( i , pos , v ) where pos is the leaf associated with address i specified by a leafmap . In addition to the tree, there is another data structure called the “stash” that holds R = O ( log n ) · ω ( 1 ) blocks which we will refer to as the 0th level in the binary tree D ′ .

P ′ ← OProg ( P ) : Given the complied program P ′ that is comprised from a sequence of virtual read/write operations do the following:

Read / Write : This algorithm follows the same outline as the algorithm from Simple ORAM and traverses the tree from the root to the leaf pos = leafmap ( i ) , searching for the tuple ( i , pos , v ) . When this tuple is found, it is removed from the bucket and ( i , pos ′ , v ) is written to the stash, setting leafmap ( i ) = pos ′ (where pos ′ is picked in random).

Eviction : For each Read / Write operation we preform the eviction procedure twice. Namely, we first choose two random non-overlapping paths denoted by path 1 and path 2 . Let path [ ℓ ] denote the bucket associated with the ℓth level on path (where path [ 0 ] is defined as the stash and path [ 1 ] is the root). For each path ∈ { path 1 , path 2 } do the following:

Read all buckets on path and generate an array deepest [ 1 , … , d + 1 ] , where deepest [ i ] = ℓ means that the deepest block in path [ 0 , i − 1 ] that can legally reside in path [ i ] is now in level ℓ < i (the buckets are read one by one and the array deepest is generated gradually).

Generate an array target [ 0 , d + 1 ] based on deepest , where target [ i ] stores the level the deepest block in path [ i ] will be evicted to.

Read all buckets on path and for each bucket, remove the deepest block and write it in target [ i ] . More precisely, initialize dest , temp = ⊥ and for i ∈ [ 0 , d + 1 ] do: (1) Read bucket path [ i ] . (2) If i = dest then write temp on the bucket path [ i ] . (3) If target [ i ] ≠ ⊥ , then temp = the deepest block from path [ i ] and dest = target [ i ] .

Security with unprotected memory access (UMA) is a weaker security notion for GRAM schemes. In this variant, the attacker may learn the initial contents of the memory D, as well as the complete memory-access pattern throughout the computation including the locations being read/written and their contents. In particular, we let MemAccess = { i t read , v t write } t ∈ [ T ] correspond to the outputs of the CPU-step circuits during the execution of P D ( x ) . Security requires the existence of a simulator SIM where: ( D ˜ , x ˜ , P ˜ ) ≈ c SIM ( κ , T , P , y , D , MemAccess ) where D ˜ ← GData ( κ , D ) , x ˜ ← GInput ( κ , x , k Inp ) , ( P ˜ , k Inp ) ← GProg ( κ , n , T , P ) , and y = P D ( x ) . In [15], Gentry et al. have proven a transformation from any GRAM with UMA security into a scheme with full security by applying a symmetric encryption scheme and an ORAM to respectively hide the memory content and the access pattern to the memory. Their transformation initiated the study of GRAMs with the weaker UMA security notion, which is obviously sufficient for establishing feasibility results but not for understanding bottlenecks and the concrete efficiency of protocols for RAM programs.

2.7. Garbled RAM

Analogously to garbled circuits for Boolean circuits [52], garbled RAM (GRAM) provide similar guarantees in the RAM model of computation. Namely, it is a non-interactive object that ensures privacy and correctness, and implies semi-honest two-round secure two-party computation when combined with OT. The standard definition of GRAM [15] is composed out of four algorithms defined as follows.

Syntax. A garbled RAM scheme consists of four PPT algorithms ( GData , GProg , GInput , GEval ) defined as follows:

Correctness. We require that for any program P, initial memory D and input x it holds that: Pr [ GEval D ˜ ( P ˜ , D ˜ , x ˜ ) = P D ( x ) ] = 1 where D ˜ ← GData ( D , k ) , ( P ˜ , k Inp ) ← GProg ( P , k , n , t ) and x ˜ ← GInput ( x , k Inp ) .

Security. We require that there exists a simulator SIM such that: ( D ˜ , P ˜ , x ˜ ) ≈ c SIM ( n , t , P , y ) where D ˜ ← GData ( D , k ) , ( P ˜ , k Inp ) ← GProg ( P , k , n , t ) and x ˜ ← GInput ( x , k Inp ) .

2.8. The details of [13] GRAM

The GRAM from [13] that is based on one-way functions and uses a novel mechanism to prevent rollback while avoiding the circularity issue that arises in [33]. Loosely speaking, given a garbled memory that is built using a tree, the evaluator traverses this tree while obliviously regenerating the nodes that it visits using fresh PRF keys that are hardwired within the CPU-circuits. Moreover, each non-leaf node contains information that allows to extract the input key labels for the next garbled circuit in the chain of the CPU-steps. Upon concluding the tree navigation and reaching a leaf, the data is being accessed via that leaf and the process repeats itself for the next RAM instruction. In more details, in this construction each internal node node is associated with a PRF key r that is encrypted under a PRF key associated with node ’s parent, and each memory access is translated into a sequence of d ′ − 1 navigation circuits (where d ′ is the depth of the [13] tree) and a step circuit. During the evaluation, each navigation circuit outputs a translation mapping that allows the evaluator to learn the input label for the next node (either the left or the right child of node ) based on the path to the read position in the memory. In addition, the circuit refreshes the PRF key associated with node and computes a new set of PRF values based on this new key to be stored on node . The step circuit finally performs the read or write operation. When proving security via the UMA setting first, this technique incurs a multiplicative overhead of d ′ on top of the running time of the program since for each memory access the evaluator has to traverse a tree of depth d ′ and only then perform the actual operation.

Data garbling: D ˜ ← GData ( D , k ) . Let the memory data D be of size n where each block is of size κ, then the garbled memory D ˜ is a binary tree of depth d where the real data is associated with the leaves of the tree. Furthermore, the content of the internal nodes is determined based on computations made using the PRF keys r i , j ∈ { 0 , 1 } κ where i is the level (or the depth) of the tree and j is the index of that node within the ith level (where the ith level includes 2 i keys). Namely, these keys are used to encrypt the data or the input labels keys for the next CPU-step circuit. In particular at the leaves level, the 2 κ bits D j κ … D j κ + 2 κ − 1 are encrypted using the key r d − 1 , ⌊ j / 2 ⌋ for every j, where the first κ bits are encrypted with a tag left and the remaining κ bits are encrypted with the tag right . In addition, each value within an internal node is encrypted by the key that is associated with its parent node. The concrete realization requires that each bit of the key r i , j is encrypted under the key r i − 1 , ⌊ j / 2 ⌋ .

Program garbling: ( P ˜ , k Inp ) ← GProg ( P , k , n , t ) . Each CPU-step in the original program P is performed using d steps in this scheme, where the first d − 1 steps navigate the tree to the required data block whereas the last step performs the CPU-step of the program on this block and continues with the next CPU-step cycle. In the following, we provide the details of these two sub-circuits navigation and step:

Navigation circuit. The navigation circuits enable to traverse the tree. Each circuit n a v i , j for i ∈ [ T ] and j ∈ [ d ] , denotes the jth circuit within the ith group of circuits that navigates the jth level of the tree while computing the ith CPU-step. This circuit takes as input two PRF keys x , y and a location L. In addition, it is hardwired with the PRF keys s , r ′ and the labels lbl 0 left , lbl 1 left , lbl 0 right , lbl 1 right where s is a fresh key that will replace the key associated with the parent of the two nodes associated with keys x and y, and r ′ is a fresh key that will replace either x or y (depends on the location L). Moreover, the set of labels lbl ‾ b z corresponds to the input labels for the next navigation circuit with respect to the keys x and y (for z ∈ { left , right } , b ∈ { 0 , 1 } ). The output of n a v i , j is the result of the PRF F applied on the pair of keys using the parent key s and a translation table that initiates the evaluation of the next circuit in the ith group of circuits, which is either circuit n a v i , j + 1 or s t e p i . In more details, the n a v i , j circuit is defined as follows:

Step circuit. The circuit s t e p i takes as input two data items D x , D y along with the location L and the current state of the program. As before, the values r and s, as well as a set of labels lbl ‾ b z (for z ∈ { left , right } , b ∈ { 0 , 1 } ) are hardcoded into this circuit, where r is a fresh key that replaces the key that is associated with the parent of D x , D y and s is the PRF key of the root of the tree. Moreover, lbl ‾ b z are the key labels for the input wires used by the next navigation circuit n a v i + 1 , 0 , which is the first navigation circuit of the next CPU-step. In more details, circuit s t e p i is defined as follows:

If L d − 1 = 0 then set D read = D x to be the data item that is required for the ith CPU-step. Upon reading D read , the evaluator computes ( state ′ , L ′ , D write ) = C CPU P ( state , D read ) where state ′ is the new state of the program, L ′ is the next location to be read from and D write is the value to overwrite location D read with. Encrypt the updated data items ( D write , D y ) (where D write replaces D x ) with their fresh parent’s key r and output write = ( L , F r ( left , D write ) , F r ( right , D y ) ) . Similarly, if L d − 1 = 1 then follows this step with D read = D y .

We next review the gradual ORAM definition in which there is no initialization phase of the compiled data where instead, the data is initialized gradually before executing the compiled program. This definition includes a new algorithm OProgInsertion replacing algorithm OData (see Definition 2.4), that outputs a compiled sequence of CPU-steps that supports potential data insertions to the memory. Upon completing the execution of this program, we obtain a gradual data structure (i.e., an incomplete tree) that contains the compiled data. Formally, a Gradual ORAM scheme consists of two algorithms ( OProgInsertion , OProg ) specified as follows:

P INS ′ ← OProgInsertion ( n ) : Takes as input the size of the memory n and outputs a compiled memory insertion program P INS ′ . On runtime, each CPU-step in P INS ′ gets as input a single memory element from the memory data D and a secret key SK as part of the initial state and outputs an updated data D ′ (arranged in a gradual data structure).

Definition 2.5.

A polynomial-time algorithm C is a Gradual ORAM compiler with computational overhead c ( · ) and memory overhead m ( · ) , if C, when given n ∈ N and a deterministic RAM program P with memory size n, outputs a program P ′ with memory size m ( n ) · n , such that for any input x ∈ { 0 , 1 } ∗ , a uniformly random key SK ∈ { 0 , 1 } κ (where κ is the security parameter) and a uniformly random string r ∈ { 0 , 1 } κ , it follows that T ( P ′ ( n , x , SK , r ) ) = c ( n ) · T ( P , n , x ) and there exists a negligible function μ such that the following properties hold:

Correctness. For any n ∈ N , any input x ∈ { 0 , 1 } ∗ , any key and uniformly random strings SK , r ∈ { 0 , 1 } κ , with probability at least 1 − μ ( κ ) , P ′ ( n , x , SK , r ) = P ( n , x ) .

Obliviousness. For any program P, initial memory data D of size n and input x, there exists a PPT simulator SIM such that ( D ′ , MemAccessInsertion , MemAccess ) ≈ c SIM ( T , n , y ) ,

where MemAccessInsertion (resp. MemAccess ) correspond to the outputs of the circuits during the execution of P INS ′ (resp. P ′ ).

3. Gradual GRAM

In this section we define the notion of gradual GRAM where the memory is not garbled separately, but rather occupied via a sequence of insert operations; details follow.

Syntax. The new garbled GRAM notion consists of four PPT algorithms ( GProg , GInputInsertion , GInput , GEval ) defined as follows:

( P ˜ , k ¯ INS Inp , k ¯ D Inp , k ¯ RAM Inp , s ) ← GProg ( P , k , n , t ) : Takes as input a program P that is represented as a sequence of T CPU-steps with memory size n and outputs a garbled program P ˜ and input garbling key labels k INS Inp , k ¯ D Inp , k ¯ RAM Inp , s . The garbled program P ˜ consists of a garbled insertion program P ˜ INS and a garbled RAM program P ˜ RAM corresponding to P. The input garbling keys k INS Inp correspond to the inputs labels of the first circuit in P ˜ INS excluding the input labels for the first element from the memory D 1 . The key s is the root PRF key generated upon running the garbling insertion program.

{ D ˜ e } e ∈ [ n ] ← GInputInsertion ( D , k ¯ D Inp ) : Takes as input a memory D of size n and insertion garbling keys k ¯ D Inp and outputs a garbled data element D ˜ e for each e ∈ [ n ] (where D ˜ e is the garbled memory for the eth address).

k ˜ ← GInput ( x , k ¯ RAM Inp , s ) : Takes as input an input x, input garbling keys k ¯ RAM Inp and root key s and outputs a garbled input k ˜ which is the set of input key labels for the first circuit in garbled RAM program P ˜ RAM .

y ← GEval ( P ˜ , k INS Inp , { D ˜ e } e ∈ [ n ] , k ˜ ) : Takes as input a garbled program P ˜ , the insertion gabling inputs keys k INS Inp , garbled data elements { D ˜ e } e ∈ [ n ] and a garbled input k ˜ and computes the output y = P D ( x ) .

Correctness. We require that for any program P, memory D and input x it holds that: Pr [ GEval ( P ˜ , k INS Inp , { D ˜ e } e ∈ [ n ] , k ˜ ) = P D ( x ) ] = 1 where ( P ˜ , k ¯ INS Inp , k ¯ D Inp , k ¯ RAM Inp , s ) ← GProg ( P , k , n , t ) , { D ˜ e } e ∈ [ n ] ← GInputInsertion ( D , k ¯ D Inp ) and k ˜ ← GInput ( x , k ¯ RAM Inp , s ) .

Security. We require that there exists a simulator SIM such that: ( P ˜ , k INS Inp , { D ˜ e } e ∈ [ n ] , k ˜ ) ≈ c SIM ( n , T , P , y ) where ( P ˜ , k ¯ INS Inp , k ¯ D Inp , k ¯ RAM Inp , s ) ← GProg ( P , k , n , t ) , { D ˜ e } e ∈ [ n ] ← GInputInsertion ( D , k ¯ D Inp ) , k ˜ ← GInput ( x , k ¯ RAM Inp , s ) and y = P D ( x ) .

3.1. The modified [13] GRAM

We next discuss how to combine the [13] GRAM with Simple/Circuit ORAMs while building the tree gradually, starting with the modified “Program Garbling” algorithm.

Program garbling: ( P ˜ , k ¯ INS Inp , k ¯ D Inp , k ¯ RAM Inp , s ) ← GProg ( P , k , n , t ) . In order to combine the GLOS construction with Simple ORAM, we extend GLOS by storing additional information on each non-leaf node. More formally, the root, denoted by n 0 , 0 , is associated with a PRF key r 0 , 0 . Moreover, each internal node n i , j is associated with a PRF key r i , j where i ∈ { 1 , … , d − 1 } refers to the node’s depth whereas j ∈ { 0 , … , 2 i − 1 } refers to its position on its row. Recall that the garbled memory is created gradually during the execution of the garbled program. Consequently, the garbled memory may correspond to an incomplete data structure, implying that upon reading some node it does not have any children. In this case, we should not output a translate table for the missing children or try to rewrite their values. To identify this case, each node will store two additional bits cdn = { cdn [ 0 ] , cdn [ 1 ] } which respectively indicate the existence of the left or right children. Namely, cdn [ 0 ] = 1 if and only if the specified node has a left child, and similarly for cdn [ 1 ] . To conclude, each non-leaf node n i , j stores three types of PRF evaluations computed under its parent’s PRF key r i − 1 , ⌊ j / 2 ⌋ (or under the key r ROOT for the case of the root):

Navigation information that includes the PRF evaluations over the key r i , j (as in GLOS).

ORAM information that includes the PRF evaluations over the bucket B i , j associated with this node. Each such bucket contains d tuples of size U of the form ( i , pos , v ) where v is the memory content for the address i and pos is the leaf index associated with that address.

Information about the children, that includes the PRF evaluations over cdn .

The leaf nodes, denoted by n d , j for j ∈ [ 0 , n − 1 ] , only contain the PRF evaluations over the bucket B d , j .

Our garbling procedure has four subroutines: (1) reading from the root, (2) reading from the internal nodes, (3) reading from a leaf and (4) the final circuit. Each subroutine outputs a translation mapping for the children of the node it is reading from (where at the leaf level the mapping is for the root), which allows to extract the input labels for the next circuit on the navigation path (where in case a child does not exist, then the translation mapping outputs labels corresponding to 0). We denote the set of input labels corresponding to a circuit in our construction, type ∈ { left , right , root } { lbl b type ‾ } b ∈ { 0 , 1 } = ( { lbl b type , 0 , k } b ∈ { 0 , 1 } , k ∈ [ κ ] ︸ navigation labels (GLOS) , { lbl b type , h , u } b ∈ { 0 , 1 } , h ∈ [ d ] , u ∈ [ U ] ︸ bucket labels , { lbl b type , c } b ∈ { 0 , 1 } , c ∈ [ 0 , 1 ] ︸ children’s labels An important building block of these subroutines is the procedure trans that outputs a translation mapping of a node. This procedure obtains the input labels of the next circuit and outputs a translate table for the PRF values associated with this node. We present its details in Fig. 2.

OPEN IN VIEWER

Fig. 2.

The translation mapping procedure.

An overview of the circuits. The program garbling procedure contains four different types of circuits: C ROOT that enables to read from the root, C INTER that enables to read from an internal (non-leaf and non-root) node, C LEAF that enables to read from a leaf node and a concluding circuit C FINAL .

As in the GLOS construction each internal circuit C INTER takes two PRF keys r left , r right associated with two adjacent nodes ( n i , j , n i , j + 1 ) in some level i and an auxiliary input aux which includes additional information such as the state state and the index level. The circuit is also given the buckets B left and B right stored on these nodes, and the values cdn left and cdn right corresponding to the children’s information of each node. Finally, the circuit is hardwired with fresh PRF keys r ′ , r and the input labels to the next circuit { lbl b left ‾ , lbl b right ‾ } b ∈ { 0 , 1 } .

Upon given these inputs, each circuit runs a CPU-step of the Simple ORAM which uses one of the buckets { B left , B right } according to the reading location stored at aux and outputs an updated bucket B write . It further outputs a tuple ( aux ′ , write , translate ) where aux ′ denote an updated auxiliary information, write consists of the values to be written into nodes n i , j , n i , j + 1 and translate consists of the translation mapping for the two children in the next level on the navigation path using the labels { lbl b left ‾ , lbl b right ‾ } b ∈ { 0 , 1 } . Moreover, the write output contains PRF evaluation under the fresh key r ′ which replaces the key associated with the parent of the nodes n i , j , n i , j + 1 . The second fresh key r will replace one of the keys r left , r right which will be determined according to the reading location. Namely, the PRF evaluations will be computed now over the new key r and the other old key associated with the node in the other direction. Next, the updated bucket B write is written to the appropriate node together with the updated values cdn left and cdn right .

The three other circuits are described similarly to the internal circuit with the following modifications. First, the input to the root circuit includes a single PRF key r 0 , 0 , a bucket B 0 , 0 and cdn 0 , 0 . Furthermore, the leaf circuit is hardwired with the input labels of the next root circuit their output translate refers to the root, whereas the final circuit is not hardwired with any input labels. In addition, the later two circuits do not take any PRF keys. For the following formal description, we use the notation B u h , write denoting the bit u within the tuple h in the bucket B write and the notation pos [ i ] denotes the bit i in the leaf pos (which contains d bits enumerated from 1 to d). We continue with the detailed descriptions of the garbling program subroutines and circuits functionalities.

Reading from the root (circuit C ROOT ). This circuit takes as input a key associated with the root r 0 , 0 , a bucket B 0 , 0 , an auxiliary input aux = { state , t , i , i read , v read , v write } and a pair of bits cdn . For the first t < n · log n steps, the circuit also obtains i insert , v insert (per entry from the real memory data D). In addition, the circuit is hardwired with the PRF keys s , r ′ and labels { lbl b left ‾ , lbl b right ‾ } b ∈ { 0 , 1 } where s and r ′ are fresh PRF keys that will respectively replace the keys r ROOT and r 0 , 0 . In more details,

Initialize pos , B temp = NULL and set B read = B 0 , 0 , r trans = r 0 , 0 .

If t = 0 set mode = Read / Write . Else set mode = 1 − mode .7

⁷

We use the variable mode to interchange between Read / Write and Eviction . We abuse notation and denote by 1 − mode the “opposite” (namely, the other) value of mode .

If t < n · log n run ( pos , B write , B temp ) ← C CPU P INS ′ ( i insert , v insert , i , pos , B read , B temp ) ︸ Simple ORAM insertion else, run ( state ′ , pos , B write , B temp , i read , v read , v write ) ← C CPU P ′ ( state , i , mode , pos , B read , B temp , i read , v read , v write ) ︸ Simple ORAM read/write instruction for the compiled P’

Set transLeft = trans ( r trans , left , { lbl b left ‾ } b ∈ { 0 , 1 } ) .

Set transRight = trans ( r trans , right , { lbl b right ‾ } b ∈ { 0 , 1 } ) .

Set translate = lbl 0 left ‾ ‖ lbl 0 right ‾ , if cdn = 00 ; translate = lbl 0 left ‾ ‖ transRight , if cdn = 01 ; translate = transLeft ‖ lbl 0 right ‾ , if cdn = 10 ; translate = transLeft ‖ transRight , if cdn = 11 ; .

Below, IsOtherNode contains a one-bit flag to indicate the existence of a node that does not reside on the reading path. The next circuit uses IsOtherNode in order to check whether to rewrite the other node that is not on the path. Specifically, if pos [ i + 1 ] = 0 then set cdn [ 0 ] = 1 and IsOtherNode = cdn [ 1 ] , else set cdn [ 1 ] = 1 and IsOtherNode = cdn [ 0 ] .

Set write = ( root , { F s ( root , 0 , k , r k ′ ) } k ∈ [ κ ] ‖ { F s ( root , h , u , B u h , write ) } h ∈ [ d ] , u ∈ [ U ] ‖ F s ( root , 0 , cdn [ 0 ] ) ‖ F r ′ ( root , 1 , cdn [ 1 ] ) )

Output: aux ′ = ( { state ′ , IsOtherNode , pos , t + 1 , 1 , mode , B temp , i read , v read , v write } , translate , write ) .

Reading from an internal node (circuit C INTER ). This circuit takes as input two PRF keys r left and r right that are associated with the two nodes ( n i , j , n i , j + 1 ) , their corresponding buckets B left and B right , an auxiliary input aux = { t , i , state , IsOtherNode , pos , mode , B temp , i read , v read , v write } and the two values cdn left and cdn right . In addition, the circuit is hardwired with the PRF keys r ′ , r , and labels { lbl b left ‾ , lbl b right ‾ } b ∈ { 0 , 1 } where r ′ is the key associated with the parent’s node of ( n i , j , n i , j + 1 ) and r is a fresh key that will replace either r left or r right (depends on the value pos ). In more details,

Deciding whether the next move is left or right based on the next position bit. Namely, if pos [ i ] = 0 then set type = left , else type = right . Also set B read = B type , r trans = r type , cdn = cdn type .

Initializing i insert , v insert = NULL (since these inputs are only used at the root level).

Run Steps 3–6 from the procedure for C ROOT .

If pos [ i + 1 ] = 0 then set cdn type [ 0 ] = 1 and IsOtherNode = cdn type [ 1 ] , else cdn type [ 1 ] = 1 and IsOtherNode = cdn type [ 0 ] .

Set write = ( type , { F r ′ ( type , 0 , k , r k ) } k ∈ [ κ ] ‖ { F r ′ ( type , h , u , B u h , write ) } h ∈ [ d ] , u ∈ [ U ] ‖ F r ′ ( type , 0 , cdn type [ 0 ] ) ‖ F r ′ ( type , 1 , cdn type [ 1 ] ) )

Set also the output writing values for the opposite direction, which is not on the reading path. writeOpp = ( type ‾ , 8 { F r ′ ( type ‾ , 0 , k , r k type ‾ ) } k ∈ [ κ ] ‖ { F r ′ ( type ‾ , h , u , B u h , type ‾ ) } h ∈ [ d ] , u ∈ [ U ] ‖ F r ′ ( type ‾ , 0 , cdn type ‾ [ 0 ] ) ‖ F r ′ ( type ‾ , 1 , cdn type ‾ [ 1 ] ) )

⁸

The syntax type ‾ refers to the opposite of the variable type . For example, if type = left then type ‾ = right .

If IsOtherNode = 1 then set write = write ‖ writeOpp .

Output: aux ′ = ( state , IsOtherNode , pos , t + 1 , i + 1 , mode , B temp , i read , v read , v write , translate , write ) .

Reading from a leaf (circuit C LEAF ). This circuit takes as input two buckets B left and B right that are associated with the two nodes ( n i , j , n i , j + 1 ) and an auxiliary input aux = { t , i , state , mode , IsOtherNode , pos , B temp , i read , v read , v write } . In addition, the circuit is hardwired with the PRF keys r ′ , s and the labels { lbl b root ‾ } b ∈ { 0 , 1 } , where r ′ is the key associated with the parent’s node of ( n i , j , n i , j + 1 ) and s is the key of the parent of r 0 , 0 . In more details,

If pos [ i − 1 ] = 0 then set type = left , else type = right . Also set B read = B type .

Set i insert , v insert = NULL .

Run Step 3 from the procedure for C ROOT .

Set translate = trans ( s , root , { lbl b root ‾ } b ∈ { 0 , 1 } )

Set write = ( type , { F r ′ ( type , h , u , B u h , write ) } h ∈ [ d ] , u ∈ [ U ] )

Set writeOpp = ( type ‾ , { F r ′ ( type , h , u , B u h , type ‾ ) } h ∈ [ d ] , k ∈ [ U ] )

If IsOtherNode = 1 then set write = write ‖ writeOpp .

Output: aux ′ = ( { state , pos , t + 1 , 0 , mode , i read , v read , v write } , translate , write )

The final step (circuit C FINAL ). The circuit takes as input two buckets B left and B right that are associated with the two nodes ( n i , j , n i , j + 1 ) and an auxiliary input aux = { t , state , IsOtherNode , pos , B temp , i read , v read , v write } . In addition, the circuit is hardwired with a PRF key r ′ where r ′ is the key associated with the parent’s node of ( n i , j , n i , j + 1 ) . In more details,

Run Steps 1–3 and 5–7 from the procedure for C LEAF .

Output: ( state ′ , write ) .

3.2. The complete GRAM construction

Summarizing the descriptions of the above four subroutines, the final garbling procedure consists of multiple instances of these circuits. More specifically, our complete garbling program procedure consists of two sub-procedures: the insertion program garbling denoted by GProg INS and the actual garbling RAM program P denoted by GProg RAM . These sub-procedures are described in Figs 3 and 4. Each of them call algorithm GCircuit in order to garble each circuit. Note that each circuit is hardwired with the input labels for the next circuit and we therefore need to garble the circuits in the opposite order.

In the insertion garbled program GProg INS , the program only follows the Eviction procedure as defined in the Simple ORAM. Therefore, for each memory entry D e for e ∈ [ n ] , the garbled RAM traverses the tree from the root to some leaf implying that it will consist of one instance of C ROOT , ( d − 1 ) instances of C INTER and one instance of C LEAF , where in the last step one instance of C LEAF is replaced with an instance of C FINAL . This program garbling outputs a set of garbled circuits denoted by { C ˜ τ , i } where τ ∈ [ n ] is the time step and i ∈ [ 0 , d ] is the level in the tree. As in the GLOS construction, we parse the inputs labels of each garbled circuit C ˜ τ , i as lbl ‾ τ , i = ( lbl ‾ τ , i , read , lbl ‾ τ , i , aux ) , where the former set of labels correspond to the inputs r left , r right , B left , B right , cdn left and cdn right (that should be read from the memory) and are embedded in the previous circuit. Whereas the later set of labels correspond to the data elements from D and other information that depends on the input such as the state.

On the other hand, for each memory access in the garbled RAM program GProg RAM , the program traverses the tree twice, reading two root-to-leaf paths (one in Read / Write mode and another in Eviction mode) implying that the garbled program will consist of two instances of C ROOT , 2 · ( d − 1 ) instances of C INTER and two instances of C LEAF , where in the last step one instance of C LEAF is replaced with an instance of C FINAL . The garbling RAM program GProg RAM outputs a set of garbled circuits denoted by { C ˜ τ , p , i } where τ ∈ [ n + 1 , n + T ] is a RAM step, p ∈ { 0 , 1 } indicates whether this is the first or the second root-to-leaf pass and i ∈ [ 0 , d ] is the tree level. Note that the same circuits are garbled for both paths where the functionality differs as a function of the mode.

Program garbling GProg . Informally, the garbling procedure GProg ( P , k , n , t ) proceeds as follows:

Run ( P ˜ INS , k INS Inp , k ¯ D Inp , s ) ← GProg INS ( k , n ) .

Run ( P ˜ RAM , k ¯ RAM Inp ) ← GProg RAM ( P , k , n , t ) .

Output ( P ˜ = { P ˜ INS , P ˜ RAM } , k INS Inp , k ¯ D Inp , k ¯ RAM Inp , s ) .

OPEN IN VIEWER

Fig. 3.

The description of GProg INS .

OPEN IN VIEWER

Fig. 4.

The description of GProg RAM .

Data elements garbling { D ˜ e } e ∈ [ n ] ← GInputInsertion ( D , k ¯ D Inp ) . This algorithm outputs input labels for the elements in D, namely for each { D e } e ∈ [ n ] . These labels will constitute the inputs labels to the first instance of C ˜ ROOT in the sequence of insertion circuits. Specifically, upon given the inputs ( D , k ¯ D Inp = { lbl ‾ e , 0 , i insert , v insert } e ∈ [ n ] ) , the algorithm GInputInsertion outputs { D ˜ e } = ( { lbl e γ e , 0 , i γ insert } γ ∈ [ log n ] , { lbl D e β e , 0 , v β insert } β ∈ [ U ′ ] ) , 1 ⩽ e ⩽ n where e γ is the γth bit of the index e, D e β is the βth bit in the element D e and U ′ is the size of an element in D.

Input garbling k ˜ ← GInput ( x , k ¯ RAM Inp , s ) . This algorithm outputs the input labels for the garbled program P ˜ RAM . Upon given the inputs ( x , k ¯ RAM Inp = { lbl ‾ root , lbl ‾ aux } , s ) , the algorithm proceed as follows:

Set translate = { F s ( root , 0 , k , 0 ) ⊕ lbl 0 root , 0 , k , F s ( root , 0 , k , 1 ) ⊕ lbl root , h , k } k ∈ [ κ ] { F s ( root , h , u , 0 ) ⊕ lbl 0 root , h , u , F s ( root , h , u , 1 ) ⊕ lbl root , h , u } h ∈ [ d ] , u ∈ [ U ] { F s ( root , c , 0 ) ⊕ lbl 0 root , c } c ∈ [ 0 , 1 ] { F s ( root , c , 1 ) ⊕ lbl root , c } c ∈ [ 0 , 1 ]

Set x ˜ = { lbl x σ aux , state σ } σ ∈ [ | x | ] where x σ is the σth bit of x.

Set lbl ‾ aux ′ = lbl ‾ aux / lbl ‾ aux , state (the auxiliary labels apart from state ).

Output k ˜ = { translate , x ˜ , lbl ‾ 0 aux ′ } .

Garbled evaluation y ← GEval ( P ˜ , k INS Inp , { D ˜ e } e ∈ [ n ] , k ˜ ) . This algorithm sequentially evaluates the garbled circuits created by GProg and calls procedure Eval in order to evaluate the underlying garbled circuits (see Section 2.3 for its definition) and is described in details in Fig. 5.

OPEN IN VIEWER

Fig. 5.

The description of GEval .

We conclude with the following theorem.

Theorem 3.1.

Assuming one-way functions, then our construction is secure garbled RAM scheme (cf. Section  2.7 ).

Proof overview. In this proof we construct a simulator that outputs a sequence of simulated garbled circuits generated from the end to start. Since the simulator does not know the real input values ( D , x ) it writes random values to the memory (rather than PRF evaluations). Moreover, by definition, the simulator knows only one label per input wire and hence cannot compute the complete translate table as required by the garbling program. It therefore uses random values for the missing labels in the translation mapping (denoted by rand ∗ , ∗ for the corresponding set of wires). Note that, as in the real execution, the values written to the memory must be consistent with the translate table of some future circuit. Namely, if the value α ⊕ lbl is output as part of the translate table of circuit C ˜ τ , then the value α should be written to the same location by the last circuit C ˜ τ ′ , τ ′ < τ that writes to that location. To address these limitations, the simulator maintains an updated table that contains all the values output as part of the translate table. The simulator also keeps a flag table in order to avoid accessing nodes that do not exist yet. Intuitively, in order to argue that the simulated output is indistinguishable from the real distribution, we first define a hybrid experiment Hyb for which the simulator access the real memory access locations. We then prove that the simulation and the hybrid experiment are indistinguishable, relying on the security of the Simple ORAM. Next, we follow the proof outline of GLOS and reduce security to the PRF security and privacy of garbled circuits.

Proof.

Proving Theorem 3.1 involves proving correctness and security. Correctness follows due to the correctness of the underlying garbled circuits that correctly realize the underlying functionalities. The more challenging part of the proof will be to prove security by proving the existence of a PPT simulator SIM such that: ( P ˜ , k ¯ INS Inp , { D ˜ e } e ∈ [ n ] , k ˜ ) ≈ c SIM ( κ , n , T , P , y ) where ( P ˜ , k ¯ INS Inp , k ¯ D Inp , k ¯ RAM Inp , s ) ← GProg ( κ , n , T , P ) , { D ˜ e } e ∈ [ n ] ← GInputInsertion ( κ , D , k ¯ D Inp ) , k ˜ ← GInput ( κ , x , k ¯ RAM Inp , s ) and y = P D ( x ) . We start by defining the details of simulator SIM and then prove that the simulated view is indistinguishable from the real view by a sequence of hybrid experiments. Let Osim be the simulator of the modified Simple ORAM and CircSim be the simulator of the garbled circuit. Our simulation uses the label notation lbl ‾ τ , p , i of circuit C ˜ τ , p , i to denote the keys obtained by CircSim where each input wire is associated with a single key. The simulator further uses two sub-procedures denoted by GenerateWrite and GenerateTranslate which are described in Figs 6 and 7. The sub-procedure GenerateWrite takes as input the tuple ( τ , p , i ) along with the current reading location and outputs the values to be written into two nodes in level i. The sub-procedure GenerateTranslate takes as input ( τ , p , i ) along with the current reading location and input labels and outputs a translate table for two nodes in level i + 1 . The simulator maintains two files: F VAL and F FLAGS where the former stores the values that are output by the translate table mapping for any step τ and phase p. This file is initialized with NULL and is updated during the execution. The later stores all the nodes that will be visited in any step τ and phase p (namely, the access pattern during executing the programs). That is, F FLAGS [ τ ] [ p ] [ i ] [ l ] = 1 means that the node indexed as l at level i will be accessed in step τ and phase p. This file is initialized at the beginning of the simulation and is not updated. These files are being accessed by the sub-procedures GenerateWrite and GenerateTranslate . GenerateTranslate updates the file F VAL when outputting a translate table and GenerateWrite checks it before writing. Both sub-procedures check F FLAGS in order to avoid writing or outputting a translate table to a node that does not exist.

OPEN IN VIEWER

Fig. 6.

The GenerateWrite procedure.

OPEN IN VIEWER

Fig. 7.

The GenerateTranslate procedure.

Remark 3.1.

As opposed to the garbling procedure in the real execution, we cannot simulate the garbling of the insertion program before simulating the garbling of the RAM program. This is due to the fact that the writing values output by the insertion program should be consistent with the translate table in the simulated RAM program. Consequently, the simulation will first simulate the garbling of the RAM program and then the insertion program.

The simulator SIM ( κ , n , T , P , y ) . 

Run ( MemAccess = { { L τ } τ ∈ [ n ] , { L τ p } τ ∈ [ n + 1 , … , T ] , p ∈ { 0 , 1 } } ) ← Osim ( κ , n , T , y ) 9 where

⁹

We assume that Osim outputs only the accesses to the leaves because the other accesses are determined according to the them.

{ L τ } τ ∈ [ n ] is the memory access during the insertion program and { L τ p } τ ∈ [ n + 1 , … , T ] , p ∈ { 0 , 1 } is the memory access during the RAM program.

Initialize files F VAL and F FLAGS with NULL.

For each location { L τ } τ ∈ [ n ] , traverse the tree from the root to that location and set F FLAGS [ τ ] [ 0 ] [ i ] [ l ] = 1 where i ∈ [ d ] and l is the number obtained by considering the ith higher order bits of the binary representation of location L τ . For each location { L τ p } τ ∈ [ n + 1 , … , T ] , p ∈ { 0 , 1 } , do the same and set F FLAGS [ τ ] [ p ] [ i ] [ l ] = 1 .

For τ ∈ { T + n , … , n + 1 } and for p ∈ { 0 , 1 }

Garbling of C FINAL : If τ = T + n ∧ p = 1 compute ( C ˜ T , 1 , d , lbl ‾ T , 1 , d ) ← CircSim ( κ , C FINAL , write , aux ) where aux = y and write = ( GenerateWrite ( T , 1 , d , L T 1 ) ) .

Garbling of C LEAF : If τ ≠ T + n ∧ p = 1 compute ( C ˜ τ , 1 , d , lbl ‾ τ , 1 , d ) ← CircSim ( κ , C LEAF , write , translate , lbl ‾ τ + 1 , 0 , 0 , aux ) , where write = ( GenerateWrite ( τ , 1 , d , L τ 1 ) ) and translate = GenerateTranslate ( τ + 1 , 0 , 0 , L τ + 1 0 , lbl ‾ τ + 1 , 0 , 0 , read ) .

Garbling of C LEAF : If p = 0 compute ( C ˜ τ , 0 , d , lbl ‾ τ , 0 , d ) ← CircSim ( κ , C LEAF , write , translate , lbl ‾ τ , 1 , 0 , aux ) , where write = ( GenerateWrite ( τ , 0 , d , L τ 0 ) ) and translate = GenerateTranslate ( τ , 1 , 0 , L τ 1 , lbl ‾ τ , 1 , 0 , read ) .

Garbling of C INTER : For i ∈ [ d − 1 , 1 ] compute ( C ˜ τ , p , i , lbl ‾ τ , p , i ) ← CircSim ( κ , C INTER , write , translate , lbl τ , p , i + 1 , aux ) , where write = ( GenerateWrite ( τ , p , i , L τ p ) ) and translate = GenerateTranslate ( τ , p , i + 1 , L τ p , lbl ‾ τ , p , i + 1 , read ) .

Garbling of C ROOT : Compute ( C ˜ τ , p , 0 , lbl ‾ τ , p , 0 ) ← CircSim ( κ , C ROOT , write , translate , lbl τ , p , 1 , aux ) where write = ( GenerateWrite ( τ , p , 0 , L τ p ) ) and translate = GenerateTranslate ( τ , p , 1 , L τ p , lbl ‾ τ , p , 1 , read ) .

For τ ∈ { n , … , 1 }

Garbling of C FINAL : If τ = n compute ( C ˜ τ , 0 , d , lbl ‾ τ , 0 , d ) ← CircSim ( κ , C FINAL , write ) , where write = ( GenerateWrite ( τ , 0 , d , L τ ) ) and set translateForRAM = GenerateTranslate ( τ + 1 , 0 , 0 , L τ + 1 0 , lbl ‾ τ + 1 , 0 , 0 , read ) , where translateForRAM is the translate table for the first circuit in the garbling RAM program.

Garbling of C LEAF : Else, compute ( C ˜ τ , 0 , d , lbl ‾ τ , 0 , d ) ← CircSim ( κ , C LEAF , write , translate , lbl ‾ τ + 1 , 0 , 0 , aux ) , where write = ( GenerateWrite ( τ , 0 , d , L τ ) ) and translate = GenerateTranslate ( τ + 1 , 0 , 0 , L τ + 1 , lbl ‾ τ + 1 , 0 , 0 , read ) .

Garbling of C INTER : For i ∈ [ d − 1 , 1 ] compute ( C ˜ τ , 0 , i , lbl ‾ τ , 0 , i ) ← CircSim ( κ , C INTER , write , translate , lbl τ , 0 , i + 1 , aux ) , where write = ( GenerateWrite ( τ , 0 , i , L τ ) ) and translate = GenerateTranslate ( τ , 0 , i + 1 , L τ , lbl ‾ τ , 0 , i + 1 , read ) .

Garbling of C root : Compute ( C ˜ τ , 0 , 0 , lbl ‾ τ , 0 , 0 ) ← CircSim ( κ , C ROOT , write , translate , lbl τ , 0 , 1 , aux ) where write = ( GenerateWrite ( τ , 0 , 0 , L τ ) ) and translate = GenerateTranslate ( τ , 0 , 1 , L τ , lbl ‾ τ , 0 , 1 , read ) .

Set P ˜ = { { C ˜ τ , 0 , i } τ ∈ [ n ] , i ∈ [ d ] , { C ˜ τ , p , i } τ ∈ [ n 1 , … , n + T ] , p ∈ { 0 , 1 } , i ∈ [ d ] } and { D ˜ τ } τ ∈ [ n ] = { lbl ‾ τ , 0 , i insert , v insert } τ ∈ [ n ] . Let aux ∗ = aux − { i insert , v insert } then k INS Inp = { lbl ‾ 1 , 0 , aux ∗ , lbl ‾ 1 , 0 , read } and k ˜ = { lbl ‾ 1 , 0 , 0 , aux , translateForRAM } .

Output ( P ˜ , k INS Inp , { D ˜ τ } τ ∈ [ n ] , k ˜ RAM Inp ) .

This concludes the simulation. Let Sim denote the output distribution of SIM .

In order to prove indistinguishability, we first define a hybrid experiment denoted by Hyb ( D , P , x ) in which the only difference between this execution and the simulation is that the algorithm uses the real memory access and not the simulated one. Formally, instead of running step 1 in the simulation, in Hyb we run P INS ′ ← OProgInsertion ( n ) , P ′ ← OProg ( P ) , compute D ′ = P INS ′ ( D ) , P ′ D ′ ( x ) and obtain ( y , MemAccess = { { L τ } τ ∈ [ n ] , { L τ p } τ ∈ [ n + 1 , … , n + T ] , p ∈ { 0 , 1 } } )

We next prove the following claim,

Claim 3.2.

Sim and Hyb are computationally indistinguishable.

Proof.

Assume the existence of inputs D , P , x for which there exists a distinguisher B for the two distributions Sim and Hyb . We construct a distinguisher B ′ for the ORAM scheme. Note that the only difference between Sim and Hyb is in step 1, where in Sim the accessed locations are simulated whereas in Hyb the real access pattern, as determined by the real execution of the program, is in use. The challenge ( D ′ , MemAccess ) for B ′ is a list of memory accesses that is distributed according to the real or simulated distributions. Therefore, B ′ can employ this challenge with B while emulating the rest of the simulation procedure according these locations. Note that if ( D ′ , MemAccess ) are the simulated locations, then the result distribution is identically distributed to Sim and if ( D ′ , MemAccess ) correspond to the real locations then the result distribution is identically distributed to Hyb . Thus, if B distinguishes between the two hybrids Sim and Hyb then the distinguisher B ′ distinguishes between the above distribution in the ORAM scheme. □

In the next part of the proof we prove the next claim,

Claim 3.3.

( P ˜ , k INS Inp , { D ˜ e } e ∈ [ n ] , k ˜ ) ≈ c Hyb ( D , P , x ) .

Proof.

From here on, the proof is very similar to the proof from [13] and we therefore give the a high level of the proof. We define a sequence of hybrid experiments where we gradually replace a garbled circuit with a simulated one. Let H τ , p , i − 1 be the experiment where all circuits till circuit C ˜ τ , p , i − 1 have been successfully replaced with simulated circuits. In hybrid H τ , p , i we want to replace C ˜ τ , p , i with simulated circuit (For τ > n , if p = 0 and i = d then the next hybrid is H τ , 1 , 0 and the circuit to be replaced is C ˜ τ , 1 , 0 . If p = 1 and i = d then the next hybrid is H τ + 1 , 0 , 0 and the circuit to be replaced is C ˜ τ + 1 , 0 , 0 ). The outputs of circuit C τ , p , i − 1 are:

Translate table for both directions using a PRF key from level i − 1 : translate = { F r i − 1 ( type , 0 , k , 0 ) ⊕ lbl 0 type , 0 , k , F r i − 1 ( type , 0 , k , 1 ) ⊕ lbl type , h , k } k ∈ [ κ ] { F r i − 1 ( type , h , u , 0 ) ⊕ lbl 0 type , h , u , F r i − 1 ( type , h , u , 1 ) ⊕ lbl type , h , u } h ∈ [ d ] , u ∈ [ U ] { F r i − 1 ( type , c , 0 ) ⊕ lbl 0 type , c } c ∈ [ 0 , 1 ] { F r i − 1 ( type , c , 1 ) ⊕ lbl type , c } c ∈ [ 0 , 1 ]

Write to the two children in level i − 1 using a fresh PRF key r ′ (these children may be used to decrypt the translate table computed in circuit C ˜ τ ′ , p , i − 2 for some τ ′ > τ . Hence, we will replace the evaluation with PRF key with random value only in hybrid H τ , p , i − 1 ).

In sub-hybrid H PRF τ , p , i we wish to replace the PRF evaluation computed with the key r i − 1 with a random value. As in [13] the key r i − 1 is used to compute PRF evaluation only in two circuits: in the translate table of circuit C τ , p , i − 1 and in the output write of the circuit C τ ′ , p , i for some τ ′ < τ . Therefore in H PRF τ , p , i we replace PRF evaluation computed with the key r i − 1 in both circuits as following:

In the circuit C τ , p , i − 1 replace the translate table for both directions with random values: translate = { r type , 0 , k , 0 ⊕ lbl 0 type , 0 , k , r type , 0 , k , 1 ⊕ lbl type , h , k } k ∈ [ κ ] { r type , h , u , 0 ⊕ lbl 0 type , h , u , r type , h , u , 1 ⊕ lbl type , h , u } h ∈ [ d ] , u ∈ [ U ] { r type , c , 0 ⊕ lbl 0 type , c } c ∈ [ 0 , 1 ] { r type , c , 1 ⊕ lbl type , c } c ∈ [ 0 , 1 ]

In the output write of the circuit C τ ′ , p , i : Write to two children in level i the real values that are stored in that nodes. Namely, if the indexes of the nodes are ( i , j ) and ( i , j + 1 ) , then write = { r left , 0 , k , r k ( i , j ) } k ∈ [ κ ] , { r left , h , u , B k ( i , j ) } h ∈ [ d ] , u ∈ [ U ] r cdnLeft , 0 , cdn ( i , j ) [ 0 ] , r cdnLeft , 1 , cdn ( i , j ) [ 1 ] { r right , 0 , k , r k ( i , j + 1 ) } k ∈ [ κ ] , { r right , h , u , B k ( i , j + 1 ) } h ∈ [ d ] , u ∈ [ U ] r cdnRight , 0 , cdn ( i , j + 1 ) [ 0 ] , r cdnRight , 1 , cdn ( i , j + 1 ) [ 1 ] This is necessary because in this sub-hybrid, the circuit C ˜ τ , p , i is still real circuit and needs to get as inputs the correct values.

Note that the only difference between the hybrid H τ , p , i − 1 and the sub-hybrid H PRF τ , p , i is the values in these two mentioned points. In H τ , p , i − 1 , they are PRF evaluation and in H PRF τ , p , i , they are random values. Assume by contradiction the existence of an adversary A that distinguishes between the output of H τ , p , i − 1 and H PRF τ , p , i for infinitely many n’s, then it is easy to build a distinguisher D PRF that can distinguish between PRF evaluation and random function. Hence, we can say that the hybrid H τ , p , i − 1 and the sub-hybrid H PRF τ , p , i are computational indistinguishable.

In the sub-hybrid H Enc τ , p , i we replace the labels that are not decrypted with random strings. Namely, in the circuit C τ , p , i − 1 replace the translate table for both directions as following: translate = r type , 0 , k ⊕ lbl type , 0 , k rand left , 0 , k k ∈ [ κ ] r type , h , u ⊕ lbl type , h , u rand left , h , u h ∈ [ d ] , k ∈ [ U ] r type , c ⊕ lbl type , c rand type , c c ∈ [ 0 , 1 ] Because the keys in the sub-hybrid H PRF τ , p , i are chosen at random, the other label is information theortically hidden and hence the sub-hybrid H Enc τ , p , i and the sub-hybrid H PRF τ , p , i are indistinguishable.

In the last sub-hybrid H circuit τ , p , i we replace the circuit C ˜ τ , p , i with a simulated one. The only difference between H circuit τ , p , i and H Enc τ , p , i is the circuit C ˜ τ , p , i which can be simulated or real. The security of the garbled circuit ensures that one can not distinguish between these two circuits and hence H circuit τ , p , i and H Enc τ , p , i are computational indistinguishable. Note that H circuit τ , p , i = H τ , p , i and hence also H τ , p , i is indistinguishable from H τ , p , i − 1 . □

Efficiency. In our construction, the size of the garbled program, as well as the time it takes to create and evaluate it is O ( ( n + T ) · poly ( κ , U · B ˜ ) ) where an ORAM bucket contains B ˜ tuples of size U (where in the Simple ORAM B ˜ = O ( log n ) whereas in the Circuit ORAM B ˜ = O ( 1 ) for internal nodes and O ( log n ) stash size). Moreover, the overall running time of GProg and GInputInsertion , as well as the running time of GEval is O ( ( n + T ) · log n ) . Note that there is a tradeoff between the unit size that is read per access and the overall number of accesses per original access. The analyze of most tree-based ORAMs is based on reading a single memory unit per access which implies that the running time is O ( log 2 n ) per one original access. On the other hand, when reading the whole bucket in a single access as we analyze above, the overhead per one original access is O ( log n ) but requires garbling larger CPU-steps circuits. A similar analysis holds for the [13] GRAM as well.