Gradual GRAM and secure computation for RAM programs 1

Abstract

Despite the fact that the majority of applications encountered in practice today are captured more efficiently by RAM programs, the area of secure two-party computation (2PC) has seen tremendous improvement mostly for Boolean circuits. One of the most studied objects in this domain is garbled circuits. Analogously, garbled RAM (GRAM) provide similar security guarantees for RAM programs with applications to constant round 2PC. In this work we consider the notion of gradual GRAM which requires no memory garbling algorithm. Our approach provides several qualitative advantages over prior works due to the conceptual similarity to the analogue garbling mechanism for Boolean circuits. We next revisit the GRAM construction from (In STOC (2015) 449–458) and improve it in two orthogonal aspects: match it directly with tree-based ORAMs and explore its consistency with gradual ORAM.

Keywords

Secure computation garbled RAM ORAM

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].

1.1. Constant round 2PC for RAM programs

Similarly to two-party protocols for Boolean circuits, achieving constant round for RAM programs is carried out by adapting the garbled circuits technique [52] to support RAM computations [12,13,15,33]. Nevertheless, as opposed to classic garbled circuits where the computation is large and the inputs are relatively small, in RAM programs the accessed memory can be huge whereas the running time of the program is typically much smaller (e.g., polylogarithmic in the memory size). Informally, garbled RAM (GRAM) is a non-interactive object that garbles the memory D into $\tilde{D}$ , the program P into $\tilde{P}$ and the input x into $\tilde{x}$ such that only $P^{D} (x)$ (the execution of such a program) is revealed from $\tilde{D}, \tilde{P}, \tilde{x}$ . Moreover, the size of $\tilde{D}$ (reps. $\tilde{x}$ ) is proportional to D (resp. x), and the size and evaluation-time of $\tilde{P}$ grows with the running-time of $P^{D} (x)$ . At the heart of every GRAM construction lies a mechanism that prevents the evaluator from rolling back and evaluates the CPU circuits on an older version of the data elements (namely, before the most recent update took place). Consequently, memory garbling algorithms must be embedded with authenticating tools (even in the semi-honest setting). As for Boolean circuits, combined with semi-honest oblivious transfer, GRAM immediately implies semi-honest 2PC for RAM programs.

In order to hide the access pattern to the memory, all these schemes are built on top of ORAMs. Recall that the original motivation of ORAM was to protect memory accesses to the physical RAM (or to a server with a large storage capacity), by some remote CPU (or by a client with a small storage). Nevertheless, in the distributed setting, the memory is initially empty and is occupied on the fly (see [1]). Therefore, it makes no sense to initially run the garbled memory algorithm. Another drawback is regarding the amplification from semi-honest to malicious security, which either involves using zero-knowledge proofs for highly complicated statements or running a distributed protocol for the memory initialization. For instance, proving correctness within [13] requires proving the correctness of $κ^{2}$ PRF evaluation per tree node. Moreover, current GRAM constructions do not support the useful offline/online paradigm, where most of the work can be offloaded to an offline phase which is independent of the parties’ inputs.2

²
While some of the computation of these garbled memory algorithms can be carried out offline, it requires storing a large state that grows with the memory size.

Finally, the security analysis of these constructions have been proven relative to the weaker Unprotected Memory Access (UMA) notion, where the attacker may learn the initial contents of the memory D as well as the complete memory-access pattern throughout the computation. A transformation from any GRAM scheme with UMA security into one with full security has shown in [15].3

Informally, the transformation encrypts the memory elements and apply an ORAM construction to hide the access pattern.

Furthermore, with the exception of the GRAM from [33],4

⁴

Note that this construction suffers from a circularity issue in its security analysis; see [15] for a detailed discussion.

all prior constructions garble the memory using a tree that is built on top of the data. Namely, in [12,13] the leaves are associated with the memory contents, whereas in [15] a binary tree is added on top of the original data in order to construct Oblivious RAM with Predictably Timed Writes.

These drawbacks demonstrate that there is much room for improving the current state of affairs of GRAM schemes both theoretically and practically.

1.2. Our results

Gradual ORAM for tree-based ORAMs. Motivated by the discussion above and the fact that all GRAM constructions are based on binary trees, we start by examining tree-based ORAM constructions and explore the flexible notion of gradual ORAM. This notion is an extension of the classic notion of ORAM that does not require an initialization phase to compile the data. Instead, a new algorithm is considered, that handles the memory insertions separately and can be skipped directly to the RAM program set of instructions. An immediate advantage that is derived by the flexibility of gradual ORAM is resizability [35]. Namely, the inherent dependence on a fixed-size tree is removed, allowing flexible storage. We stress that this concept is not new, but for the sake of completeness we provide a formal definition (Section 2.9).

Gradual GRAM. Next we extend the notion of GRAM and consider an analogue gradual GRAM notion with no memory garbling algorithm. Namely, this object is defined by only two algorithms for garbling the program and the input, where all the memory operations are incorporated within the program. This modification implies that the garbling mechanism is now only involved with a sequence of small CPU-steps that are garbled using the classic garbled circuits approach. Therefore, it is conceptually closer to the analogue garbling mechanism for Boolean circuits. This new concept also introduces several advantages:

The scheme enjoys all the advancements of garbled circuits such as half gates, Free-XOR, Pipelining, and OT extension, that lead to highly optimizes semi-honest protocols. We note that garbling a large set of circuits can benefit from recent techniques for batch garbling [36] (due to garbling a large sequence of small CPU-steps).

The bulk of work (e.g., generating the garbled circuits) can be shifted to an offline phase, performed independently of the data and the parties’ inputs.

Amplifying security to the malicious setting is immediate by applying standard techniques such as cut-and-choose [30] or authenticated garbling [26,47], or any futuristic alternative approaches.

The parties can directly proceed with the program execution whenever the initial memory is empty and build the tree on the fly.

The space complexity of the garbler algorithm can be made minimal by processing each garbled circuit at the time rather than storing the entire tree of memory.

In addition, gradual GRAM can serve as a step towards supporting a broader class of data processing algorithms such as data streams or online algorithms, where the data is processed serially (compatible with memory on the fly access). We also stress that our notion maintains persistent data, where the memory updates are persistent for future executions, as similarly considered in prior work.

We next revisit the GRAM construction from [13] and improve it in two dimensions:

We first prove that it can be combined directly with tree-based ORAMs, where the best matches are with the Simple ORAM [5] and the Circuit ORAM [45] due to their root-to-leaf eviction algorithms. We observe that for some ORAM constructions it is beneficial to build a combined tree that contains both the ORAM buckets, as well as the GRAM information, and is proven directly secure rather than via UMA. This allows to reduce the number of visited nodes in the GRAM and simplifies the CPU-steps circuits; see more discussion below and a comparison in Table 1. We remark that combining a tree-based ORAM with other data structures also appeared in [50].

In addition, we observe that [13] can be made consistent with our notion of gradual GRAM, where the combined tree is built on the fly based on gradual ORAM. This requires adjusting the GRAM algorithms to support an incomplete tree while maintaining authentication. Furthermore, it allows to avoid the expensive initialization phase and saves on space resources, as the size of the tree is minimized rather then growing with the maximum size of the data. To handle the case where an internal node may not have any children, we store two additional bits that notify whether the current node has a left (resp. right) child.

Efficiency gains. To understand the quantitative differences between our gradual GRAM constructions and [13], we compare in Table 1 the number of nodes visited in the garbled memory in both cases, and the sizes of the garbled circuits involved a single ORAM access. Note first that all tree-based ORAMs require reading $O (1)$ root-to-leaf paths which implies reading $O (\log n)$ nodes per original memory access. Moreover, the GLOS construction implies a tree with $O (n \log n)$ leaves (each containing a bucket of size B). Therefore, accessing an ORAM node requires reading $\log n$ nodes, where the size of the $\log n - 1$ navigation circuits grows with $κ^{2}$ PRF evaluations whereas the leaf circuits involve $O (κ \cdot B)$ PRF evaluations.5

⁵
This is because the translation mapping in [13] involves a PRF evaluation per stored bit.

Thus, the total number of steps in GLOS is

O ((n + T) \cdot \log^{2} n)

and the overall circuits sizes of accessing a single ORAM element involve

O ((\log n - 1) \cdot κ^{2} + κ \cdot B)

PRF evaluations.

In contrast, our construction combines the ORAM tree with the GRAM tree which eliminates a factor of $\log n$ in the overhead, implying running time of $O ((n + T) \cdot \log n)$ (where the $n \cdot \log n$ overhead is due to the insertion program which may be eliminated in some cases such as when the initial memory is empty). Furthermore, each circuit involves $O (κ^{2} + κ \cdot B)$ PRF evaluations as each node is also associated with a bucket (which implies that the node’s size is larger). When instantiating the underlying ORAM with Simple ORAM each node contains a bucket of $O (\log n)$ values of size U, then we achieve circuit size proportional to $O (κ^{2} + κ \cdot U \cdot \log n)$ PRF evaluations. In the Circuit ORAM each node contains a bucket with $O (1)$ values where only the stash is of size $O (\log n)$ . Therefore in this case only the stash circuit is of size $O (κ^{2} + κ \cdot U \cdot \log n)$ , while the other circuits are of size $O (κ^{2} + κ \cdot U)$ . See Section 3.2 for more discussion.

Table 1

Communication and computation costs for the different GRAMs schemes. We use n to denote the number of memory entries, B the bucket size, κ the security parameter and U the size of a value

Approach	Overall Number of Steps	Overall CPU-Steps Circuits Sizes per a Single ORAM Access
[13]	$O ((n + T) \cdot \log^{2} n)$	$O ((\log n - 1) \cdot κ^{2} + κ \cdot B)$
Gradual [13] + Simple ORAM	$O ((n + T) \cdot \log n)$	$O (κ^{2} + κ \cdot U \cdot \log n)$
Gradual [13] + Circuit ORAM	$O ((n + T) \cdot \log n)$	$O (κ^{2} + κ \cdot U)$

Extending to the multi-party setting. Due to the conceptual similarity to the garbled circuits approach for Boolean circuits, our approach is also easily extendable to the multi-party setting as well by applying different distributed garbling approaches [2,23,48]. These protocols scale much better than when running a distributed protocol for computing the garbled memory algorithm as done in all prior work, due to all recent optimizations.

Conference version. This full version is based on [22] which was published in SCN 2020. This version includes a complete description and proof of our gradual GRAM construction as well as more elaborated discussion on the modeling of gradual GRAM and the extension based on prior work.

2. Preliminaries

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

We specify next the definition of computationally indistinguishability.

Definition 2.1.
Let $X = {X (a, κ)}_{a \in {0, 1}^{}, κ \in N}$ and $Y = {Y (a, κ)}_{a \in {0, 1}^{}, κ \in N}$ be two distribution ensembles. We say that X and Y are computationally indistinguishable, denoted $X \overset{c}{\approx} Y$ , if for every PPT machine $D$ , there exists a negligible function $negl$ such that: $\begin{matrix} | Pr [D (X (a, κ), 1^{κ}) = 1] - Pr [D (Y (a, κ), 1^{κ}) = 1] | ⩽ negl (κ) . \end{matrix}$

2.1. Pseudorandom functions

Definition 2.2.
Let $F : {0, 1}^{κ} \times {0, 1}^{m} \mapsto {0, 1}^{m}$ be an efficient, length preserving, keyed function. $F$ is a pseudorandom function if for all polynomial-time distinguishers $D$ , there exists a negligible function $negl$ such that: $\begin{matrix} | Pr [D^{F_{k} (\cdot)} (1^{κ}) = 1] - Pr [D^{f (\cdot)} (1^{κ}) = 1] | ⩽ negl (κ), \end{matrix}$ where $F_{k}$ is a keyed function with a randomly chosen key k and f is a random function from ${0, 1}^{m} \mapsto {0, 1}^{m}$ . The probability in both cases is taken over the randomness of $D$ as well.
2.2. Garbled circuits

The notion of garbled circuits was first introduced by [52]. A garbling scheme for a Boolean circuit is a tuple of PPT algorithms $(GCircuit, Eval)$ where $GCircuit$ is the circuit garbling procedure and $Eval$ is the corresponding evaluation procedure. The sender performs the $GCircuit$ procedure which encodes a Boolean circuit that computes some PPT function f, in a way that (computationally) hides from the receiver any information but the function’s output. In the garbled circuit, each individual wire w of the circuit will be associated with two labels denoted as ${lbl}_{0}^{w}$ and ${lbl}_{1}^{w}$ . We denote the set of input and output wires by $Inp (C)$ and $Out (C)$ respectively. For the purpose of our protocols, we distinct two types of outputs: plain outputs and labeled outputs, where the plain output values do not require labels (namely, the evaluation procedure outputs these values in the clear), whereas labeled output values are associated with output labels. We continue with a formal definition of garbled circuits:

Definition 2.3 (Garbled circuits.).

A circuit garbling scheme consists of the following two polynomial-time procedures:

The circuit garbling procedure: $\begin{matrix} (\tilde{C}, {w, {lbl}_{b}^{w}}_{w \in Inp (C), b \in {0, 1}}) \leftarrow GCircuit (1^{κ}, C, {w, {lbl}_{b}^{w}}_{w \in Out (C), b \in {0, 1}}) \end{matrix}$ The procedure takes as input a security parameter κ, a circuit C and labels of the output wires and outputs a garbled circuit $\tilde{C}$ and the labels of the input wires.

The evaluation procedure: $\begin{matrix} ({w, o_{w}}_{w \in Out (C)}) \leftarrow Eval (\tilde{C}, {w, {lbl}_{x_{w}}^{w}}_{w \in Inp (C)}) \end{matrix}$ The procedure takes as input a garbled circuit $\tilde{C}$ and a set of input labels corresponds to the input x, and outputs ( ${w, o_{w}}_{w \in Out (C)}$ where each $o_{w}$ is either $y_{w}$ or ${lbl}_{y_{w}}^{w}$ depending on whether the output is being given in the clear or as a label only.

Correctness. For correctness, we require that for any circuit C and any input x, we have that: $\begin{matrix} Pr [Eval (\tilde{C}, {w, {lbl}_{x_{w}}^{w}}_{w \in Inp (C)}) = {w, y_{w}, {lbl}_{y_{w}}^{w}}_{w \in Out (C)}] = 1 \end{matrix}$ where $y = C (x)$ .

Privacy. For privacy, we require that there exists a PPT simulator $CircSim$ such that for any $C, x$ and labels ${w, {lbl}_{b}^{w}}_{w \in Out (C), b \in {0, 1}}$ , we have that: $\begin{matrix} {(\tilde{C}, {w, {lbl}_{x_{w}}^{w}})}_{w \in Inp (C)} \overset{c}{\approx} CircSim {(1^{κ}, {w, {lbl}_{y_{w}}^{w}})}_{w \in Out (C)} \end{matrix}$ where $y = C (x)$ .

Authenticity. In the authenticity game, the adversary obtains a set of garbled circuits and garbled inputs for which it can only output a valid garbling of an invalid output with a negligible probability. This notion was first introduced by Bellare et al. in [3] and is not captured by the above privacy definition. Authenticity is required since it must be ensured that a corrupted evaluator does not evaluate the CPU-steps circuits on multiple inputs. We note that this concern is raised even in the presence of semi-honest adversaries.

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}, \dots, y_{c}) = {(P_{1} (x_{1}), \dots, 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: $\begin{matrix} C_{CPU}^{P} ({state}_{t}, v_{t}^{read}) = ({state}_{t + 1}, i_{t + 1}^{read}, v_{t + 1}^{write}), 1 ⩽ t ⩽ T \end{matrix}$ 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 \in [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^{'} \leftarrow OData (D, SK)$ : Takes as input a memory D and a symmetric secret key $SK$ and outputs an encoded memory $D^{'}$ .

$P^{'} \leftarrow 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 (\cdot)$ and memory overhead $m (\cdot)$ , if C, when given $n \in N$ and a deterministic RAM program P with memory size n, outputs a program $P^{'}$ with memory size $m (n) \cdot n$ , such that for any input $x \in {0, 1}^{}$ , uniformly random key $SK \in {0, 1}^{κ}$ (where κ is the security parameter) and uniformly random string $r \in {0, 1}^{κ}$ , it follows that $T (P^{'} (n, x, SK, r)) = c (n) \cdot T (P, n, x)$ and there exists a negligible function μ such that the following properties hold:
Correctness. For any $n \in N$ , any input $x \in {0, 1}^{}$ , any key and uniformly random string $SK, r \in {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 \in N$ , any two inputs, uniformly random keys and uniformly random strings: $x_{1}, x_{2} \in {0, 1}^{*}$ , ${SK}_{1}, {SK}_{2}, r_{1}, r_{2} \in {0, 1}^{κ}$ respectively, if $T (P_{1} (n, x_{1})) = T (P_{2} (n, x_{2}))$ and $P_{1}^{'} \leftarrow C (n, P_{1}, ρ_{1})$ , $P_{2}^{'} \leftarrow 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^{'} \leftarrow 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^{'} \leftarrow 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: $\begin{matrix} C_{CPU}^{P} ({state}_{t}, v_{t}^{read}) = ({state}_{t + 1}, i_{t + 1}^{read}, v_{t + 1}^{write}), 1 ⩽ t ⩽ T \end{matrix}$

Then $OProg$ outputs the complied program $P^{'}$ that is represented as a sequence of at most $T^{'} = 2 \times log n \times 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.

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^{'} \leftarrow 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) \cdot ω (1)$ blocks which we will refer to as the 0th level in the binary tree $D^{'}$ .

$P^{'} \leftarrow 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 \in {path 1, path 2}$ do the following:

Read all buckets on $path$ and generate an array $deepest [1, \dots, 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 \in [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] \neq ⊥$ , then $temp =$ the deepest block from $path [i]$ and $dest = target [i]$ .

2.6. Security with Unprotected Memory Access (UMA)

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 \in [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: $\begin{matrix} (\tilde{D}, \tilde{x}, \tilde{P}) \overset{c}{\approx} SIM (κ, T, P, y, D, MemAccess) \end{matrix}$ where $\tilde{D} \leftarrow GData (κ, D), \tilde{x} \leftarrow GInput (κ, x, k^{Inp}), (\tilde{P}, k^{Inp}) \leftarrow 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:

$\tilde{D} \leftarrow GData (D, k)$ : Takes as input a memory $D \in {0, 1}^{n}$ and a key k, and outputs the garbled memory $\tilde{D}$ .

$(\tilde{P}, k^{Inp}) \leftarrow GProg (P, k, n, t)$ : takes a key k and a description of a RAM program P with memory-size n and run-time consisting of t CPU steps, and outputs a garbled program $\tilde{P}$ and input garbling key labels $k^{Inp}$ .

$\tilde{x} \leftarrow GInput (x, k^{Inp})$ : Takes as input a small input x and input garbling key labels $k^{Inp}$ , and outputs a garbled input $\tilde{x}$ .

$y \leftarrow {GEval}^{\tilde{D}} (\tilde{P}, \tilde{D}, \tilde{x})$ : Takes as input a garbled program $\tilde{P}$ , garbled memory data $\tilde{D}$ and garbled input $\tilde{x}$ and computes the output $y = P^{D} (x)$ . We model $GEval$ as a RAM program that can read and write to arbitrary locations of its memory initially containing $\tilde{D}$ .

Correctness. We require that for any program P, initial memory D and input x it holds that: $Pr [{GEval}^{\tilde{D}} (\tilde{P}, \tilde{D}, \tilde{x}) = P^{D} (x)] = 1$ where $\tilde{D} \leftarrow GData (D, k), (\tilde{P}, k^{Inp}) \leftarrow GProg (P, k, n, t)$ and $\tilde{x} \leftarrow GInput (x, k^{Inp})$ .

Security. We require that there exists a simulator $SIM$ such that: $(\tilde{D}, \tilde{P}, \tilde{x}) \overset{c}{\approx} SIM (n, t, P, y)$ where $\tilde{D} \leftarrow GData (D, k), (\tilde{P}, k^{Inp}) \leftarrow GProg (P, k, n, t)$ and $\tilde{x} \leftarrow 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: $\tilde{D} \leftarrow GData (D, k)$ . Let the memory data D be of size n where each block is of size κ, then the garbled memory $\tilde{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} \in {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 κ} \dots 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: $(\tilde{P}, k^{Inp}) \leftarrow 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 \in [T]$ and $j \in [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 ${\overline{lbl}}_{b}^{z}$ corresponds to the input labels for the next navigation circuit with respect to the keys x and y (for $z \in {left, right}, b \in {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:

If $L_{j} = 0$ (namely, the jth bit of L equals 0), then replace x with $r^{'}$ , otherwise replace y with $r^{'}$ . Call the new key pair $\hat{x}$ , $\hat{y}$ . Encrypt this pair using their parent’s key s (hardwired) and output $\begin{matrix} write = (F_{s} (left, \hat{x}), F_{s} (right, \hat{y}), L, state) \end{matrix}$ which implies that these PRF values stored on the nodes associated with keys x and y will replace the PRF values currently written there (obviously we only replace one key amongst $(x, y)$ and thus only replace its associated PRF values).6

⁶
We note that our description is informal. Specifically, the keys are encrypted bit-by-bit implying $2 κ$ ciphertexts, as each key is of size κ.

Furthermore, the circuit outputs a translation table that enables the evaluator to obtain the input keys labels for the next level when following the path via the left node. Specifically, the circuit outputs

\begin{matrix} translate = & {\underset{padding}{\underset{︸}{F_{x} (left, 0)}} \oplus \underset{key label}{\underset{︸}{{lbl}_{0}^{left}}}, F_{x} (left, 1) \oplus {lbl}^{left}, \\ F_{x} (right, 0) \oplus {lbl}_{0}^{right}, F_{x} (right, 1) \oplus {lbl}^{right}} \end{matrix}

Similarly, if

L_{j} = 1

then the circuit outputs a translation table using the key y and replaces y with a fresh PRF key.

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 ${\overline{lbl}}_{b}^{z}$ (for $z \in {left, right}, b \in {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, ${\overline{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}$ .

Note that the following circuit $n a v_{i + 1, 0}$ restarts the navigation from layer 1 toward location $L^{'}$ (skipping layer 0). Thus, it expects to be given as input the two PRF keys $r_{1, 0}, r_{1, 1}$ . These keys are encrypted by the root key s which, as mentioned earlier, is hardwired into the current $s t e p_{i}$ circuit. Thus $s t e p_{i}$ also outputs a translation table in order to map these keys into the corresponding input labels for the circuit $n a v_{i + 1, 0}$ .

The circuit also outputs $({state}^{'}, L^{'})$ where ${state}^{'}$ is the updated state for the next CPU-step and $L^{'}$ is the next location to read from.

2.9. Gradual ORAM

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}^{'} \leftarrow 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).

$P^{'} \leftarrow OProg (P)$ : Takes as input a program P that is represented as a sequence of T CPU-steps and outputs a compiled program $P^{'}$ that is defined over the data defined by algorithm $OProgInsertion$ and computes the same function as $P^{D} (x)$ .

Definition 2.5.
A polynomial-time algorithm C is a Gradual ORAM compiler with computational overhead $c (\cdot)$ and memory overhead $m (\cdot)$ , if C, when given $n \in N$ and a deterministic RAM program P with memory size n, outputs a program $P^{'}$ with memory size $m (n) \cdot n$ , such that for any input $x \in {0, 1}^{}$ , a uniformly random key $SK \in {0, 1}^{κ}$ (where κ is the security parameter) and a uniformly random string $r \in {0, 1}^{κ}$ , it follows that $T (P^{'} (n, x, SK, r)) = c (n) \cdot T (P, n, x)$ and there exists a negligible function μ such that the following properties hold:
Correctness. For any $n \in N$ , any input $x \in {0, 1}^{}$ , any key and uniformly random strings $SK, r \in {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 $\begin{matrix} (D^{'}, MemAccessInsertion, MemAccess) \overset{c}{\approx} SIM (T, n, y), \end{matrix}$
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:

$(\tilde{P}, {\bar{k}}_{INS}^{Inp}, {\bar{k}}_{D}^{Inp}, {\bar{k}}_{RAM}^{Inp}, s) \leftarrow 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 $\tilde{P}$ and input garbling key labels $k_{INS}^{Inp}, {\bar{k}}_{D}^{Inp}, {\bar{k}}_{RAM}^{Inp}, s$ . The garbled program $\tilde{P}$ consists of a garbled insertion program ${\tilde{P}}_{INS}$ and a garbled RAM program ${\tilde{P}}_{RAM}$ corresponding to P. The input garbling keys $k_{INS}^{Inp}$ correspond to the inputs labels of the first circuit in ${\tilde{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.

${{\tilde{D}}_{e}}_{e \in [n]} \leftarrow GInputInsertion (D, {\bar{k}}_{D}^{Inp})$ : Takes as input a memory D of size n and insertion garbling keys ${\bar{k}}_{D}^{Inp}$ and outputs a garbled data element ${\tilde{D}}_{e}$ for each $e \in [n]$ (where ${\tilde{D}}_{e}$ is the garbled memory for the eth address).

$\tilde{k} \leftarrow GInput (x, {\bar{k}}_{RAM}^{Inp}, s)$ : Takes as input an input x, input garbling keys ${\bar{k}}_{RAM}^{Inp}$ and root key s and outputs a garbled input $\tilde{k}$ which is the set of input key labels for the first circuit in garbled RAM program ${\tilde{P}}_{RAM}$ .

$y \leftarrow GEval (\tilde{P}, k_{INS}^{Inp}, {{\tilde{D}}_{e}}_{e \in [n]}, \tilde{k})$ : Takes as input a garbled program $\tilde{P}$ , the insertion gabling inputs keys $k_{INS}^{Inp}$ , garbled data elements ${{\tilde{D}}_{e}}_{e \in [n]}$ and a garbled input $\tilde{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 (\tilde{P}, k_{INS}^{Inp}, {{\tilde{D}}_{e}}_{e \in [n]}, \tilde{k}) = P^{D} (x)] = 1$ where $(\tilde{P}, {\bar{k}}_{INS}^{Inp}, {\bar{k}}_{D}^{Inp}, {\bar{k}}_{RAM}^{Inp}, s) \leftarrow GProg (P, k, n, t)$ , ${{\tilde{D}}_{e}}_{e \in [n]} \leftarrow GInputInsertion (D, {\bar{k}}_{D}^{Inp})$ and $\tilde{k} \leftarrow GInput (x, {\bar{k}}_{RAM}^{Inp}, s)$ .

Security. We require that there exists a simulator $SIM$ such that: $(\tilde{P}, k_{INS}^{Inp}, {{\tilde{D}}_{e}}_{e \in [n]}, \tilde{k}) \overset{c}{\approx} SIM (n, T, P, y)$ where $(\tilde{P}, {\bar{k}}_{INS}^{Inp}, {\bar{k}}_{D}^{Inp}, {\bar{k}}_{RAM}^{Inp}, s) \leftarrow GProg (P, k, n, t)$ , ${{\tilde{D}}_{e}}_{e \in [n]} \leftarrow GInputInsertion (D, {\bar{k}}_{D}^{Inp})$ , $\tilde{k} \leftarrow GInput (x, {\bar{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: $(\tilde{P}, {\bar{k}}_{INS}^{Inp}, {\bar{k}}_{D}^{Inp}, {\bar{k}}_{RAM}^{Inp}, s) \leftarrow 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 \in {1, \dots, d - 1}$ refers to the node’s depth whereas $j \in {0, \dots, 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 \in [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 \in {left, right, root}$ $\begin{array}{rcl} {\overline{{lbl}_{b}^{type}}}_{b \in {0, 1}} & = & (\underset{navigation labels (GLOS)}{\underset{︸}{{{lbl}_{b}^{type, 0, k}}_{b \in {0, 1}, k \in [κ]}}}, \\ \underset{bucket labels}{\underset{︸}{{{lbl}_{b}^{type, h, u}}_{b \in {0, 1}, h \in [d], u \in [U]}}}, \underset{children’s labels}{\underset{︸}{{{lbl}_{b}^{type, c}}_{b \in {0, 1}, c \in [0, 1]}}} \end{array}$ 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.

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 ${\overline{{lbl}_{b}^{left}}, \overline{{lbl}_{b}^{right}}}_{b \in {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 ${\overline{{lbl}_{b}^{left}}, \overline{{lbl}_{b}^{right}}}_{b \in {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 \cdot 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 ${\overline{{lbl}_{b}^{left}}, \overline{{lbl}_{b}^{right}}}_{b \in {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 \cdot log n$ run $\begin{array}{rcl} (pos, B^{write}, B^{temp}) \leftarrow \underset{Simple ORAM insertion}{\underset{︸}{C_{CPU}^{P_{INS}^{'}} (i^{insert}, v^{insert}, i, pos, B^{read}, B^{temp})}} \end{array}$ else, run $\begin{array}{l} ({state}^{'}, pos, B^{write}, B^{temp}, i^{read}, v^{read}, v^{write}) \\ \leftarrow \underset{Simple ORAM read/write instruction for the compiled P’}{\underset{︸}{C_{CPU}^{P^{'}} (state, i, mode, pos, B^{read}, B^{temp}, i^{read}, v^{read}, v^{write})}} \end{array}$

Set $transLeft = trans (r^{trans}, left, {\overline{{lbl}_{b}^{left}}}_{b \in {0, 1}})$ .

Set $transRight = trans (r^{trans}, right, {\overline{{lbl}_{b}^{right}}}_{b \in {0, 1}})$ .

Set $\begin{matrix} \{\begin{matrix} translate = \overline{{lbl}_{0}^{left}} ‖ \overline{{lbl}_{0}^{right}}, & if cdn = 00; \\ translate = \overline{{lbl}_{0}^{left}} ‖ transRight, & if cdn = 01; \\ translate = transLeft ‖ \overline{{lbl}_{0}^{right}}, & if cdn = 10; \\ translate = transLeft ‖ transRight, & if cdn = 11; \end{matrix}\} . \end{matrix}$

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 $\begin{matrix} write = & (root, {F_{s} (root, 0, k, r_{k}^{'})}_{k \in [κ]} ‖ {F_{s} (root, h, u, B_{u}^{h, write})}_{h \in [d], u \in [U]} \\ ‖ F_{s} (root, 0, cdn [0]) ‖ F_{r^{'}} (root, 1, cdn [1])) \end{matrix}$

Output: $\begin{array}{rcl} {aux}^{'} & = & ({{state}^{'}, IsOtherNode, pos, t + 1, 1, mode, B^{temp}, i^{read}, v^{read}, v^{write}}, \\ translate, write) . \end{array}$

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 ${\overline{{lbl}_{b}^{left}}, \overline{{lbl}_{b}^{right}}}_{b \in {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 $\begin{matrix} write = & (type, {F_{r^{'}} (type, 0, k, r_{k})}_{k \in [κ]} ‖ {F_{r^{'}} (type, h, u, B_{u}^{h, write})}_{h \in [d], u \in [U]} \\ ‖ F_{r^{'}} (type, 0, {cdn}^{type} [0]) ‖ F_{r^{'}} (type, 1, {cdn}^{type} [1])) \end{matrix}$

Set also the output writing values for the opposite direction, which is not on the reading path. $\begin{matrix} writeOpp = & (\overline{type},^{8} {F_{r^{'}} (\overline{type}, 0, k, r_{k}^{\overline{type}})}_{k \in [κ]} \\ ‖ {F_{r^{'}} (\overline{type}, h, u, B_{u}^{h, \overline{type}})}_{h \in [d], u \in [U]} \\ ‖ F_{r^{'}} (\overline{type}, 0, {cdn}^{\overline{type}} [0]) ‖ F_{r^{'}} (\overline{type}, 1, {cdn}^{\overline{type}} [1])) \end{matrix}$

⁸

The syntax $\overline{type}$ refers to the opposite of the variable $type$ . For example, if $type = left$ then $\overline{type} = right$ .

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

Output: $\begin{array}{rcl} {aux}^{'} & = & (state, IsOtherNode, pos, t + 1, i + 1, mode, B^{temp}, i^{read}, v^{read}, \\ v^{write}, translate, write) . \end{array}$

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 $\begin{matrix} aux = {t, i, state, mode, IsOtherNode, pos, B^{temp}, i^{read}, v^{read}, v^{write}} . \end{matrix}$ In addition, the circuit is hardwired with the PRF keys $r^{'}, s$ and the labels ${\overline{{lbl}_{b}^{root}}}_{b \in {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, {\overline{{lbl}_{b}^{root}}}_{b \in {0, 1}})$

Set $write = (type, {F_{r^{'}} (type, h, u, B_{u}^{h, write})}_{h \in [d], u \in [U]})$

Set $\begin{matrix} writeOpp = & (\overline{type}, {F_{r^{'}} (type, h, u, B_{u}^{h, \overline{type}})}_{h \in [d], k \in [U]}) \end{matrix}$

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

Output: $\begin{array}{rcl} {aux}^{'} & = & ({state, pos, t + 1, 0, mode, i^{read}, v^{read}, v^{write}}, \\ translate, write) \end{array}$

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 \in [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 ${{\tilde{C}}_{τ, i}}$ where $τ \in [n]$ is the time step and $i \in [0, d]$ is the level in the tree. As in the GLOS construction, we parse the inputs labels of each garbled circuit ${\tilde{C}}_{τ, i}$ as ${\overline{lbl}}^{τ, i} = ({\overline{lbl}}^{τ, i, read}, {\overline{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 \cdot (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 ${{\tilde{C}}_{τ, p, i}}$ where $τ \in [n + 1, n + T]$ is a RAM step, $p \in {0, 1}$ indicates whether this is the first or the second root-to-leaf pass and $i \in [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 $({\tilde{P}}_{INS}, k_{INS}^{Inp}, {\bar{k}}_{D}^{Inp}, s) \leftarrow {GProg}_{INS} (k, n)$ .

Run $({\tilde{P}}_{RAM}, {\bar{k}}_{RAM}^{Inp}) \leftarrow {GProg}_{RAM} (P, k, n, t)$ .

Output $(\tilde{P} = {{\tilde{P}}_{INS}, {\tilde{P}}_{RAM}}, k_{INS}^{Inp}, {\bar{k}}_{D}^{Inp}, {\bar{k}}_{RAM}^{Inp}, s)$ .

Fig. 3.

The description of ${GProg}_{INS}$ .

Fig. 4.

The description of ${GProg}_{RAM}$ .

Data elements garbling ${{\tilde{D}}_{e}}_{e \in [n]} \leftarrow GInputInsertion (D, {\bar{k}}_{D}^{Inp})$ . This algorithm outputs input labels for the elements in D, namely for each ${D_{e}}_{e \in [n]}$ . These labels will constitute the inputs labels to the first instance of ${\tilde{C}}_{ROOT}$ in the sequence of insertion circuits. Specifically, upon given the inputs $(D, {\bar{k}}_{D}^{Inp} = {{\overline{lbl}}^{e, 0, i^{insert}, v^{insert}}}_{e \in [n]})$ , the algorithm $GInputInsertion$ outputs $\begin{matrix} {{\tilde{D}}_{e}} = ({{lbl}_{e_{γ}}^{e, 0, i_{γ}^{insert}}}_{γ \in [log n]}, {{lbl}_{D_{e_{β}}}^{e, 0, v_{β}^{insert}}}_{β \in [U^{'}]}), 1 ⩽ e ⩽ n \end{matrix}$ 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 $\tilde{k} \leftarrow GInput (x, {\bar{k}}_{RAM}^{Inp}, s)$ . This algorithm outputs the input labels for the garbled program ${\tilde{P}}_{RAM}$ . Upon given the inputs $(x, {\bar{k}}_{RAM}^{Inp} = {{\overline{lbl}}^{root}, {\overline{lbl}}^{aux}}, s)$ , the algorithm proceed as follows:

Set $\begin{matrix} translate = [\begin{matrix} {F_{s} (root, 0, k, 0) \oplus {lbl}_{0}^{root, 0, k}, \\ F_{s} {(root, 0, k, 1) \oplus {lbl}^{root, h, k}}}_{k \in [κ]} \\ {F_{s} (root, h, u, 0) \oplus {lbl}_{0}^{root, h, u}, \\ F_{s} {(root, h, u, 1) \oplus {lbl}^{root, h, u}}}_{h \in [d], u \in [U]} \\ {F_{s} (root, c, 0) \oplus {lbl}_{0}^{root, c}}_{c \in [0, 1]} \\ {F_{s} (root, c, 1) \oplus {lbl}^{root, c}}_{c \in [0, 1]} \end{matrix}] \end{matrix}$

Set $\tilde{x} = {{lbl}_{x_{σ}}^{aux, {state}_{σ}}}_{σ \in [| x |]}$ where $x_{σ}$ is the σth bit of x.

Set ${\overline{lbl}}^{{aux}^{'}} = {\overline{lbl}}^{aux} / {\overline{lbl}}^{aux, state}$ (the auxiliary labels apart from $state$ ).

Output $\tilde{k} = {translate, \tilde{x}, {\overline{lbl}}_{0}^{{aux}^{'}}}$ .

Garbled evaluation $y \leftarrow GEval (\tilde{P}, k_{INS}^{Inp}, {{\tilde{D}}_{e}}_{e \in [n]}, \tilde{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.

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 $α \oplus lbl$ is output as part of the translate table of circuit ${\tilde{C}}^{τ}$ , then the value α should be written to the same location by the last circuit ${\tilde{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: $\begin{matrix} (\tilde{P}, {\bar{k}}_{INS}^{Inp}, {{\tilde{D}}_{e}}_{e \in [n]}, \tilde{k}) \overset{c}{\approx} SIM (κ, n, T, P, y) \end{matrix}$ where $\begin{matrix} (\tilde{P}, {\bar{k}}_{INS}^{Inp}, {\bar{k}}_{D}^{Inp}, {\bar{k}}_{RAM}^{Inp}, s) \leftarrow GProg (κ, n, T, P), \end{matrix}$ ${{\tilde{D}}_{e}}_{e \in [n]} \leftarrow GInputInsertion (κ, D, {\bar{k}}_{D}^{Inp})$ , $\tilde{k} \leftarrow GInput (κ, x, {\bar{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 ${\overline{lbl}}^{τ, p, i}$ of circuit ${\tilde{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.

Fig. 6.

The $GenerateWrite$ procedure.

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 $\begin{matrix} (MemAccess = {{L_{τ}}_{τ \in [n]}, {L_{τ_{p}}}_{τ \in [n + 1, \dots, T], p \in {0, 1}}}) \leftarrow Osim (κ, n, T, y)^{9} \end{matrix}$ where

⁹

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

{L_{τ}}_{τ \in [n]}

is the memory access during the insertion program and

{L_{τ_{p}}}_{τ \in [n + 1, \dots, T], p \in {0, 1}}

is the memory access during the RAM program.

Initialize files $F_{VAL}$ and $F_{FLAGS}$ with NULL.

For each location ${L_{τ}}_{τ \in [n]}$ , traverse the tree from the root to that location and set $F_{FLAGS} [τ] [0] [i] [l] = 1$ where $i \in [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}}}_{τ \in [n + 1, \dots, T], p \in {0, 1}}$ , do the same and set $F_{FLAGS} [τ] [p] [i] [l] = 1$ .

For $τ \in {T + n, \dots, n + 1}$ and for $p \in {0, 1}$

Garbling of $C_{FINAL}$ : If $τ = T + n \land p = 1$ compute $\begin{matrix} ({\tilde{C}}_{T, 1, d}, {\overline{lbl}}^{T, 1, d}) \leftarrow CircSim (κ, C_{FINAL}, write, aux) \end{matrix}$ where $aux = y$ and $write = (GenerateWrite (T, 1, d, L_{T_{1}}))$ .

Garbling of $C_{LEAF}$ : If $τ \neq T + n \land p = 1$ compute $\begin{matrix} ({\tilde{C}}_{τ, 1, d}, {\overline{lbl}}^{τ, 1, d}) \leftarrow CircSim (κ, C_{LEAF}, write, translate, {\overline{lbl}}^{τ + 1, 0, 0, aux}), \end{matrix}$ where $write = (GenerateWrite (τ, 1, d, L_{τ_{1}}))$ and $translate = GenerateTranslate (τ + 1, 0, 0, L_{τ + 1_{0}}, {\overline{lbl}}^{τ + 1, 0, 0, read})$ .

Garbling of $C_{LEAF}$ : If $p = 0$ compute $\begin{matrix} ({\tilde{C}}_{τ, 0, d}, {\overline{lbl}}^{τ, 0, d}) \leftarrow CircSim (κ, C_{LEAF}, write, translate, {\overline{lbl}}^{τ, 1, 0, aux}), \end{matrix}$ where $write = (GenerateWrite (τ, 0, d, L_{τ_{0}}))$ and $translate = GenerateTranslate (τ, 1, 0, L_{τ_{1}}, {\overline{lbl}}^{τ, 1, 0, read})$ .

Garbling of $C_{INTER}$ : For $i \in [d - 1, 1]$ compute $\begin{matrix} ({\tilde{C}}_{τ, p, i}, {\overline{lbl}}^{τ, p, i}) \leftarrow CircSim (κ, C_{INTER}, write, translate, {lbl}^{τ, p, i + 1, aux}), \end{matrix}$ where $write = (GenerateWrite (τ, p, i, L_{τ_{p}}))$ and $translate = GenerateTranslate (τ, p, i + 1, L_{τ_{p}}, {\overline{lbl}}^{τ, p, i + 1, read})$ .

Garbling of $C_{ROOT}$ : Compute $\begin{matrix} ({\tilde{C}}_{τ, p, 0}, {\overline{lbl}}^{τ, p, 0}) \leftarrow CircSim (κ, C_{ROOT}, write, translate, {lbl}^{τ, p, 1, aux}) \end{matrix}$ where $write = (GenerateWrite (τ, p, 0, L_{τ_{p}}))$ and $\begin{matrix} translate = GenerateTranslate (τ, p, 1, L_{τ_{p}}, {\overline{lbl}}^{τ, p, 1, read}) . \end{matrix}$

For $τ \in {n, \dots, 1}$

Garbling of $C_{FINAL}$ : If $τ = n$ compute $\begin{matrix} ({\tilde{C}}_{τ, 0, d}, {\overline{lbl}}^{τ, 0, d}) \leftarrow CircSim (κ, C_{FINAL}, write), \end{matrix}$ where $write = (GenerateWrite (τ, 0, d, L_{τ}))$ and set $\begin{matrix} translateForRAM = GenerateTranslate (τ + 1, 0, 0, L_{τ + 1_{0}}, {\overline{lbl}}^{τ + 1, 0, 0, read}), \end{matrix}$ where $translateForRAM$ is the translate table for the first circuit in the garbling RAM program.

Garbling of $C_{LEAF}$ : Else, compute $\begin{matrix} ({\tilde{C}}_{τ, 0, d}, {\overline{lbl}}^{τ, 0, d}) \leftarrow CircSim (κ, C_{LEAF}, write, translate, {\overline{lbl}}^{τ + 1, 0, 0, aux}), \end{matrix}$ where $write = (GenerateWrite (τ, 0, d, L_{τ}))$ and $translate = GenerateTranslate (τ + 1, 0, 0, L_{τ + 1}, {\overline{lbl}}^{τ + 1, 0, 0, read})$ .

Garbling of $C_{INTER}$ : For $i \in [d - 1, 1]$ compute $\begin{matrix} ({\tilde{C}}_{τ, 0, i}, {\overline{lbl}}^{τ, 0, i}) \leftarrow CircSim (κ, C_{INTER}, write, translate, {lbl}^{τ, 0, i + 1, aux}), \end{matrix}$ where $write = (GenerateWrite (τ, 0, i, L_{τ}))$ and $translate = GenerateTranslate (τ, 0, i + 1, L_{τ}, {\overline{lbl}}^{τ, 0, i + 1, read})$ .

Garbling of $C_{root}$ : Compute $\begin{matrix} ({\tilde{C}}_{τ, 0, 0}, {\overline{lbl}}^{τ, 0, 0}) \leftarrow CircSim (κ, C_{ROOT}, write, translate, {lbl}^{τ, 0, 1, aux}) \end{matrix}$ where $write = (GenerateWrite (τ, 0, 0, L_{τ}))$ and $\begin{matrix} translate = GenerateTranslate (τ, 0, 1, L_{τ}, {\overline{lbl}}^{τ, 0, 1, read}) . \end{matrix}$

Set $\tilde{P} = {{{\tilde{C}}_{τ, 0, i}}_{τ \in [n], i \in [d]}, {{\tilde{C}}_{τ, p, i}}_{τ \in [n_{1}, \dots, n + T], p \in {0, 1}, i \in [d]}}$ and $\begin{matrix} {{\tilde{D}}_{τ}}_{τ \in [n]} = {{\overline{lbl}}^{τ, 0, i^{insert}, v^{insert}}}_{τ \in [n]} . \end{matrix}$ Let ${aux}^{*} = aux - {i^{insert}, v^{insert}}$ then $k_{INS}^{Inp} = {{\overline{lbl}}^{1, 0, {aux}^{*}}, {\overline{lbl}}^{1, 0, read}}$ and $\tilde{k} = {{\overline{lbl}}^{1, 0, 0, aux}, translateForRAM}$ .

Output $(\tilde{P}, k_{INS}^{Inp}, {{\tilde{D}}_{τ}}_{τ \in [n]}, {\tilde{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}^{'} \leftarrow OProgInsertion (n), P^{'} \leftarrow OProg (P)$ , compute $D^{'} = P_{INS}^{'} (D)$ , $P^{' D^{'}} (x)$ and obtain $\begin{matrix} (y, MemAccess = {{L_{τ}}_{τ \in [n]}, {L_{τ_{p}}}_{τ \in [n + 1, \dots, n + T], p \in {0, 1}}}) \end{matrix}$

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.

$(\tilde{P}, k_{INS}^{Inp}, {{\tilde{D}}_{e}}_{e \in [n]}, \tilde{k}) \overset{c}{\approx} 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 ${\tilde{C}}_{τ, p, i - 1}$ have been successfully replaced with simulated circuits. In hybrid $H^{τ, p, i}$ we want to replace ${\tilde{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 ${\tilde{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 ${\tilde{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$ : $\begin{matrix} translate = [\begin{matrix} {F_{r^{i - 1}} (type, 0, k, 0) \oplus {lbl}_{0}^{type, 0, k}, \\ F_{r^{i - 1}} {(type, 0, k, 1) \oplus {lbl}_{type, h, k}}}_{k \in [κ]} \\ {F_{r^{i - 1}} (type, h, u, 0) \oplus {lbl}_{0}^{type, h, u}, \\ F_{r^{i - 1}} {(type, h, u, 1) \oplus {lbl}_{type, h, u}}}_{h \in [d], u \in [U]} \\ {F_{r^{i - 1}} (type, c, 0) \oplus {lbl}_{0}^{type, c}}_{c \in [0, 1]} \\ {F_{r^{i - 1}} (type, c, 1) \oplus {lbl}_{type, c}}_{c \in [0, 1]} \end{matrix}] \end{matrix}$

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 ${\tilde{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: $\begin{matrix} translate = [\begin{matrix} {r^{type, 0, k, 0} \oplus {lbl}_{0}^{type, 0, k}, \\ r^{type, 0, k, 1} \oplus {lbl}_{type, h, k}}_{k \in [κ]} \\ {r^{type, h, u, 0} \oplus {lbl}_{0}^{type, h, u}, \\ r^{type, h, u, 1} \oplus {lbl}_{type, h, u}}_{h \in [d], u \in [U]} \\ {r^{type, c, 0} \oplus {lbl}_{0}^{type, c}}_{c \in [0, 1]} \\ {r^{type, c, 1} \oplus {lbl}_{type, c}}_{c \in [0, 1]} \end{matrix}] \end{matrix}$

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 $\begin{matrix} write = [\begin{matrix} {r^{left, 0, k, r_{k}^{(i, j)}}}_{k \in [κ]}, \\ {r^{left, h, u, B_{k}^{(i, j)}}}_{h \in [d], u \in [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 \in [κ]}, \\ {r^{right, h, u, B_{k}^{(i, j + 1)}}}_{h \in [d], u \in [U]} \\ r^{cdnRight, 0, {cdn}^{(i, j + 1)} [0]}, r^{cdnRight, 1, {cdn}^{(i, j + 1)} [1]} \end{matrix}] \end{matrix}$ This is necessary because in this sub-hybrid, the circuit ${\tilde{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: $\begin{matrix} translate = \{\begin{matrix} {[\begin{matrix} r^{type, 0, k} \oplus {lbl}^{type, 0, k} \\ {rand}^{left, 0, k} \end{matrix}]}_{k \in [κ]} \\ {[\begin{matrix} r^{type, h, u} \oplus {lbl}^{type, h, u} \\ {rand}^{left, h, u} \end{matrix}]}_{h \in [d], k \in [U]} \\ {[\begin{matrix} r^{type, c} \oplus {lbl}^{type, c} \\ {rand}^{type, c} \end{matrix}]}_{c \in [0, 1]} \end{matrix}\} \end{matrix}$ 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 ${\tilde{C}}_{τ, p, i}$ with a simulated one. The only difference between $H_{circuit}^{τ, p, i}$ and $H_{Enc}^{τ, p, i}$ is the circuit ${\tilde{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) \cdot poly (κ, U \cdot \tilde{B}))$ where an ORAM bucket contains $\tilde{B}$ tuples of size U (where in the Simple ORAM $\tilde{B} = O (\log n)$ whereas in the Circuit ORAM $\tilde{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) \cdot \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.

4. Constant round semi-honest 2PC for RAM programs

In this section we describe our two-party semi-honest protocol for RAM programs, which follows immediately from our GRAM and any semi-honest oblivious transfer. The main difference of our protocol compared to prior protocols is the lack of a memory initialization phase.

Protocol 1.

Semi honest 2PC

Input:S has input $x_{S}$ and R has input $x_{R}$ . S also has a memory D of size n.

Auxiliary inputs: A description of a program P that is represented as a sequence of at most T CPU-steps.

The protocol:

S runs $\begin{matrix} (\tilde{P}, {\bar{k}}_{INS}^{Inp}, {\bar{k}}_{D}^{Inp}, {\bar{k}}_{RAM}^{Inp}, s) \leftarrow GProg (κ, n, T, P) \end{matrix}$ and $\begin{matrix} {{\tilde{D}}_{e}}_{e \in [n]} \leftarrow GInputInsertion (κ, D, {\bar{k}}_{D}^{Inp}) \end{matrix}$ and sends $(\tilde{P}, k_{INS}^{Inp}, {{\tilde{D}}_{e}}_{e \in [n]},)$ to R.

S parses ${\bar{k}}_{RAM}^{Inp}$ as ${{\overline{lbl}}^{root}, {\overline{lbl}}^{aux}}$ . Set ${{\overline{lbl}}^{{aux}^{'}}} = {\overline{lbl}}^{aux} / {{\overline{lbl}}^{aux, {state}^{x_{S}}}, {\overline{lbl}}^{aux, {state}^{x_{R}}}}$ , where ${\overline{lbl}}^{aux, {state}^{x_{S}}}$ and ${\overline{lbl}}^{aux, {state}^{x_{R}}}$ are the input labels corresponding to the private inputs of S and R, respectively.

S computes $\begin{matrix} translate = [\begin{matrix} {F_{s} (root, 0, k, 0) \oplus {lbl}_{0}^{root, 0, k}, \\ F_{s} {(root, 0, k, 1) \oplus {lbl}_{root, h, k}}}_{k \in [κ]} \\ {F_{s} (root, h, u, 0) \oplus {lbl}_{0}^{root, h, u}, \\ F_{s} {(root, h, u, 1) \oplus {lbl}_{root, h, u}}}_{h \in [d], u \in [U]} \\ {F_{s} (root, c, 0) \oplus {lbl}_{0}^{root, c}}_{c \in [0, 1]} \\ {F_{s} (root, c, 1) \oplus {lbl}_{root, c}}_{c \in [0, 1]} \end{matrix}] \end{matrix}$

S sends ${{\overline{lbl}}_{0}^{{aux}^{'}}, {\overline{lbl}}_{x_{S}}^{aux, {state}^{x_{S}}}, translate}$ to R.

For every $γ \in [| x_{R} |]$ , S and R execute a 1-out-of-2 OT protocol in which S’s input equals $({lbl}_{0}^{aux, {state}^{x_{R}, γ}}, {lbl}_{1}^{aux, {state}^{x_{R}, γ}})$ and R’s input equals to $x_{R_{γ}}$ .

R sets $\tilde{k} = {translate, {\overline{lbl}}_{x_{S}}^{aux, {state}^{x_{S}}}, {\overline{lbl}}_{x_{R}}^{aux, {state}^{x_{R}}}, {\overline{lbl}}_{0}^{{aux}^{'}}}$ and runs $\begin{matrix} y \leftarrow GEval (\tilde{P}, k_{INS}^{Inp}, {{\tilde{D}}_{e}}_{e \in [n]}, \tilde{k}) \end{matrix}$ and outputs y.

Remark 4.1.

In a distributed RAM model there are several options to model the memory as an input. Namely, the memory can either be initialized as empty. In this case, the parties do not need to garble the insertion program and can simply start with the execution of the garbled RAM program, while the garbled memory will be created on-the-fly during evaluation. Alternatively, the memory can be shared amongst the two parties. In this case, each party inserts to every root circuit in the insertion program the input labels that correspond to its shared elements for D (while R obtains these labels by running OT instances with S).

Theorem 4.1.

Assuming a semi-honest OT, then Protocol 1 securely computes any RAM program P in the presence of semi-honest adversaries.

The proof is straightforward based on the security of our GRAM and the OT.

Footnotes

Acknowledgment

Supported by the BIU Center for Research in Applied Cryptography and Cyber Security in conjunction with the Israel National Cyber Bureau in the Prime Minister’s Office, and by ISF grant No. 1316/18.

References

Afshar ,

Hu ,

Mohassel and

Rosulek , How to efficiently evaluate RAM programs with malicious security, in: EUROCRYPT, 2015, pp. 702–729.

Beaver ,

Micali and

Rogaway , The round complexity of secure protocols (extended abstract), in: STOC, 1990, pp. 503–513.

Bellare ,

Tung Hoang and

Rogaway , Foundations of garbled circuits, in: CCS, 2012, pp. 784–796.

Buus Nielsen ,

Sebastian Nordholt ,

Orlandi and

S.S.

Burra , A new approach to practical active-secure two-party computation, in: CRYPTO, 2012, pp. 681–700.

Chung and

Pass , A simple ORAM, IACR Cryptology ePrint Archive2013 (2013), 243.

S.A.

Cook and

R.A.

Reckhow , Time-bounded random access machines, in: STOC, 1972, pp. 73–80.

Damgård ,

Keller ,

Larraia ,

Pastro ,

Scholl and

N.P.

Smart , Practical covertly secure MPC for dishonest majority – or: Breaking the SPDZ limits, in: ESORICS, 2013, pp. 1–18.

Damgård ,

Meldgaard and

J.B.

Nielsen , Perfectly secure oblivious RAM without random oracles, in: TCC, 2011, pp. 144–163.

Damgård ,

Pastro ,

N.P.

Smart and

Zakarias , Multiparty computation from somewhat homomorphic encryption, in: CRYPTO, 2012, pp. 643–662.

10.

Doerner and

Shelat , Scaling ORAM for secure computation, in: CCS, 2017, pp. 523–535.

11.

Garg ,

Gupta ,

Miao and

Pandey , Secure multiparty RAM computation in constant rounds, in: TCC, 2016, pp. 491–520.

12.

Garg ,

Lu and

Ostrovsky , Black-box garbled RAM, in: FOCS, 2015, pp. 210–229.

13.

Garg ,

Lu ,

Ostrovsky and

Scafuro , Garbled RAM from one-way functions, in: STOC, 2015, pp. 449–458. doi:10.1145/2746539.2746593.

14.

Gentry ,

K.A.

Goldman ,

Halevi ,

C.S.

Jutla ,

Raykova and

Wichs , Optimizing ORAM and using it efficiently for secure computation, in: PETS, 2013, pp. 1–18.

15.

Gentry ,

Halevi ,

Lu ,

Ostrovsky ,

Raykova and

Wichs , Garbled RAM revisited, in: EUROCRYPT, 2014, pp. 405–422.

16.

Goldreich , Towards a theory of software protection and simulation by oblivious rams, in: STOC, 1987, pp. 182–194.

17.

Goldreich and

Ostrovsky , Software protection and simulation on oblivious rams, J. ACM43(3) (1996), 431–473. doi:10.1145/233551.233553.

18.

M.T.

Goodrich ,

Mitzenmacher ,

Ohrimenko and

Tamassia , Privacy-preserving group data access via stateless oblivious RAM simulation, in: SODA, 2012, pp. 157–167.

19.

S.D.

Gordon ,

Katz ,

Kolesnikov ,

Krell ,

Malkin ,

Raykova and

Vahlis , Secure two-party computation in sublinear (amortized) time, in: CCS, 2012, pp. 513–524.

20.

Gueron ,

Lindell ,

Nof and

Pinkas , Fast garbling of circuits under standard assumptions, in: CCS, 2015, pp. 567–578.

21.

Hazay ,

Ishai and

Venkitasubramaniam , Actively secure garbled circuits with constant communication overhead in the plain model, in: TCC, 2017, pp. 3–39.

22.

Hazay and

Lilintal , Gradual GRAM and secure computation for RAM programs, in: SCN, 2020, pp. 233–252.

23.

Hazay ,

Scholl and

Soria-Vazquez , Low cost constant round MPC combining BMR and oblivious transfer, in: ASIACRYPT, 2017, pp. 598–628.

24.

Hazay and

Yanai , Constant-round maliciously secure two-party computation in the RAM model, in: TCC, 2016, pp. 521–553.

25.

Huang ,

Katz ,

Kolesnikov ,

Kumaresan and

A.J.

Malozemoff , Amortizing garbled circuits, in: CRYPTO, 2014, pp. 458–475.

26.

Ishai ,

Kushilevitz ,

Ostrovsky ,

Prabhakaran and

Sahai , Efficient non-interactive secure computation, in: EUROCRYPT, 2011, pp. 406–425.

27.

Keller and

Scholl , Efficient, oblivious data structures for MPC, in: ASIACRYPT, 2014, pp. 506–525.

28.

Keller and

Yanai , Efficient maliciously secure multiparty computation for RAM, in: EUROCRYPT, 2018, pp. 91–124.

29.

Kolesnikov and

Schneider , Improved garbled circuit: Free XOR gates and applications, in: ICALP, 2008, pp. 486–498.

30.

Lindell and

Pinkas , An efficient protocol for secure two-party computation in the presence of malicious adversaries, in: EUROCRYPT, 2007, pp. 52–78.

31.

Lindell ,

Pinkas ,

N.P.

Smart and

Yanai , Efficient constant round multi-party computation combining BMR and SPDZ, in: CRYPTO, 2015, pp. 319–338.

32.

Liu ,

Huang ,

Shi ,

Katz and

M.W.

Hicks , Automating efficient ram-model secure computation, in: IEEE Symposium on Security and Privacy, 2014, pp. 623–638.

33.

Lu and

Ostrovsky , How to garble RAM programs, in: EUROCRYPT, 2013, pp. 719–734.

34.

Miao , Cut-and-choose for garbled RAM, IACR Cryptology ePrint Archive2016 (2016), 907.

35.

Moataz ,

Mayberry ,

Blass and

Hui Chan , Resizable tree-based oblivious RAM, in: FC, 2015, pp. 147–167.

36.

Mohassel and

Rosulek , Non-interactive secure 2pc in the offline/online and batch settings, in: EUROCRYPT, 2017, pp. 425–455.

37.

J.B.

Nielsen and

Orlandi , Lego for two-party secure computation, in: TCC, 2009, pp. 368–386.

38.

Ostrovsky , Efficient computation on oblivious rams, in: STOC, 1990, pp. 514–523.

39.

Pippenger and

M.J.

Fischer , Relations among complexity measures, J. ACM26(2) (1979), 361–381. doi:10.1145/322123.322138.

40.

Ren ,

C.W.

Fletcher ,

Kwon ,

Stefanov ,

Shi ,

van Dijk and

Devadas , Constants count: Practical improvements to oblivious RAM, in: USENIX, 2015, pp. 415–430.

41.

Rindal and

Rosulek , Faster malicious 2-party secure computation with online/offline dual execution, in: USENIX, 2016, pp. 297–314.

42.

Schoenmakers and

Tuyls , Practical two-party computation based on the conditional gate, in: ASIACRYPT, 2004, pp. 119–136.

43.

Shi ,

T.-H.

Hubert Chan ,

Stefanov and

Li , Oblivious RAM with o((logn)3) worst-case cost, in: ASIACRYPT, 2011, pp. 197–214.

44.

Stefanov ,

van Dijk ,

Shi ,

T.-H.H.

Chan ,

C.W.

Fletcher ,

Ren ,

Yu and

Devadas , Path ORAM: an extremely simple oblivious RAM protocol, J. ACM65(4) (2018), 18:1–18:26. doi:10.1145/3177872.

45.

Wang ,

T.-H.H.

Chan and

Shi , Circuit ORAM: on tightness of the Goldreich–Ostrovsky lower bound, in: CCS, 2015, pp. 850–861.

46.

Wang ,

A.J.

Malozemoff and

Katz , Faster secure two-party computation in the single-execution setting, in: EUROCRYPT, 2017, pp. 399–424.

47.

Wang ,

Ranellucci and

Katz , Authenticated garbling and efficient maliciously secure two-party computation, in: CCS, 2017, pp. 21–37.

48.

Wang ,

Ranellucci and

Katz , Global-scale secure multiparty computation, in: CCS, 2017, pp. 39–56.

49.

X.S.

Wang ,

Huang ,

T.-H.

Hubert Chan ,

Shelat and

Shi , SCORAM: oblivious RAM for secure computation, in: CCS, 2014, pp. 191–202.

50.

X.S.

Wang ,

Nayak ,

Liu ,

T.-H.

Hubert Chan ,

Shi ,

Stefanov and

Huang , Oblivious data structures, in: CCS, 2014, pp. 215–226.

51.

Williams and

Sion , Single round access privacy on outsourced storage, in: CCS, 2012, pp. 293–304.

52.

A.C.

Yao , How to generate and exchange secrets (extended abstract), in: FOCS, 1986, pp. 162–167.

53.

Zahur ,

Rosulek and

Evans , Two halves make a whole – reducing data transfer in garbled circuits using half gates, in: EUROCRYPT, 2015, pp. 220–250.

Gradual GRAM and secure computation for RAM programs 1

Abstract

Keywords

1. Introduction

1.1. Constant round 2PC for RAM programs

2 While some of the computation of these garbled memory algorithms can be carried out offline, it requires storing a large state that grows with the memory size.

5 This is because the translation mapping in [13] involves a PRF evaluation per stored bit.

Definition 2.3 (Garbled circuits.).

2.3. The RAM model of computation

2.4. Oblivious RAM (ORAM)

2.7. Garbled RAM

2.8. The details of [13] GRAM

6 We note that our description is informal. Specifically, the keys are encrypted bit-by-bit implying 2 κ ciphertexts, as each key is of size κ.

3.1. The modified [13] GRAM

Footnotes

Acknowledgment

References

²
While some of the computation of these garbled memory algorithms can be carried out offline, it requires storing a large state that grows with the memory size.

⁵
This is because the translation mapping in [13] involves a PRF evaluation per stored bit.

⁶
We note that our description is informal. Specifically, the keys are encrypted bit-by-bit implying $2 κ$ ciphertexts, as each key is of size κ.