MetaDORAM: Info-Theoretic Distributed ORAM with Less Communication

Generic secure Multi-Party Computation (MPC) has historically been designed in the circuit model [40, 20, 6], in which the computation is represented as a circuit on bits or group elements. However, many computations are more naturally and efficiently implemented in the RAM model, in which it is possible to access locations in memory according to index variables. For instance, RAM is assumed in many classic algorithms and data structures, such as implementations of dictionaries, pointers, graphs and priority queues. An efficient implementation of a RAM functionality for MPC would therefore enable the adoption of generic efficient MPC.

Distributed Oblivious RAM (DORAM) is a functionality that implements RAM for MPC. It stores $n$ $d$-bit blocks of data in a secret-shared memory, and allows accesses to that memory (reads or writes) at secret-shared locations. A DORAM is secure if the views of the parties can be efficiently simulated without knowledge of any private values. See section 5 for a complete definition of the DORAM functionality.

In this work we construct information-theoretically secure DORAMs in the 3-party honest-majority setting. Our results show new asymptotic results for DORAM as a category of problem, but are also significant because the 3-party honest-majority setting is prevalent in both research and practice. An honest majority is necessary to achieve information-theoretically secure generic MPC [6], so the 3-party honest-majorty setting is the minimal setting for achieving generic information-theoretic DORAM. Furthermore, there are certain techniques which are extremely efficient in the 3-party honest majority setting (e.g. [13, 29]). Due to these factors, the 3-party honest-majority setting has received particular attention from both academia [16, 2, 18, 24, 3] and industry [7, 23].

DORAM is closely related to the problem of Oblivious RAM [21], which solves the problem of a client outsourcing memory to an untrusted server (or servers). In particular a $w$-party DORAM can be converted into an ORAM with $w$ active (i.e. computation-performing) servers and vice-versa, usually without increase in the communication cost. See section 2 for more details. Therefore, efficient DORAM is intrinsically tied to efficient multi-server active ORAM. A primary metric of this efficiency is the total amount of communication per memory access. This is often measured as the overhead, that is the number of blocks (of size $d$) of communication required per memory access.

Many DORAMs are constructed from instances of a related, well-studied, primitive called Oblivious RAM (ORAM). ORAMs were first identified by Goldreich and Ostrovsky in the 1980s [19, 33]. Consider a program which is running in a secure environment with very limited memory. The program wishes to make use of general memory on a device, but an adversary may be able to observe access patterns on this device. For instance, the program may be running in a secure enclave, such as Intel SGX [12], and may need to protect sensitive information even if the operating system is corrupted. The program can encrypt the data; this will hide the data’s contents, but will not hide the memory locations accessed by the program, which might leak sensitive information. An ORAM is an intermediary between the program and the main memory. It provides a RAM functionality to the program using the device’s memory in such a way that the access pattern on the device (the physical access pattern) reveals no information about the memory accesses by the program (the virtual access pattern), except for the number of accesses.

In a normal RAM, the cost of retrieving a block of data from memory is equal to the size of the block, denoted $d$. Adding obliviousness comes at a price; the overhead is the multiplicative increase in the number of bits that need to be accessed relative to a normal RAM. Goldreich initially presented an ORAM that had $O(\sqrt{n}\log (n))$ overhead, where $n$ is the number of blocks of memory [19], Ostrovsky constructed the first solution with poly-logarithmic overhead of $O({\log }^3(n))$ [33, 34] (the so-called “Hierarchical” solution). A series of improvements reduced the overhead to $O({\log }^2(n))$ [38, 22], $O({\log }^2(n)/\log (\log (n)))$ [26, 9], $O(\log (n)\log (\log (n)))$ [36] and finally $O(\log (n))$ [4, 5] (i.e. accessing $O(\log (n)d)$ bits of memory). This final result matches the proven asymptotic lower bound of $\mathrm{\Omega }(\log (n))$ [21, 27, 28, 25, 37]. These ORAMs consider the setting where the untrusted memory is passive (i.e. performs no computation on behalf of the ORAM) and the ORAM only has enough memory to store $\mathrm{\Theta }(1)$ blocks (and $\mathrm{\Theta }(1)$ $\kappa$-bit PRF keys).

ORAM was quickly recognized as a solution to another challenge: outsourcing memory in a network such as the internet. Here, a client with limited memory capacity wishes to store data on an untrusted server such that the access pattern on the server’s memory leaks no information about the actual memory access pattern by the client. The formalism of the original ORAM use-case is immediately applicable, with the client taking the place of the secure environment and the server replacing the device memory. However, this new application led several works to consider extensions of the model. First, the server is likely to also have significant computational resources, so may be able to perform computation to reduce communication overhead, a variant referred to as active ORAM [15, 11]. Second, some works observed that the client could easily interact with multiple servers, which under appropriate conditions could be assumed to not collude [31, 1, 10]. This was referred to as multi-server ORAM.

ORAM can be used to construct Distributed Oblivious RAM (DORAM). Any client-server ORAM can be transformed into a DORAM by evaluating the client’s circuit inside of a secure computation and allowing one of the parties to act as a server, as was first observed in [35]. There is now no trusted client. Instead, there is a “virtual client” that is simulated by a secure computation. Furthermore, the extensions to the ORAM model that resulted from the memory outsourcing application are immediately relevant to DORAMs. Since DORAMs already have multiple non-colluding parties, they can trivially take advantage of multi-server ORAMs by having the parties act as different servers. Since the parties already perform computation as part of the MPC protocol, they can naturally perform the computation needed by servers in an active ORAM. In general, a $s$-server active ORAM tolerating $t$ corrupt parties can be transformed into a $(w,t)$-secure DORAM protocol for any $w\ge s$ by simulating the client in a $(w,t)$-secure MPC and having each server’s role taken by a distinct party. Note that it is also possible to convert a DORAM into a multi-server active ORAM by a trivial transformation. Any $(w,t)$-secure DORAM can also be converted to a $(w,t)$-secure multi-server active ORAM by each server acting as one party, and by the client initially secret-sharing their query to the servers, and the servers sending the client the shares to reconstruct the result.

While simulating an ORAM client in a MPC protocol is always possible, doing so may increase the communication costs of the protocol, or increase the number of parties required. If information-theoretic security is required, the MPC requires an honest majority so at least 3 parties are required even if the ORAM only uses 1 or 2 servers. Furthermore, any computation which was performed locally by the client, requiring no communication, must instead be evaluated within a MPC protocol. Depending on the computational complexity of the client, the communication cost of simulating the client may increase the total asymptotic communication costs. (In contrast, converting a DORAM to a multi-server ORAM will never increase the asymptotic communication, as it only requires 1 secret-sharing and 1 reconstruction.)

Table 1 presents the communication cost of the best prior information-theoretic secure DORAMs and of the DORAMs presented in this work. Note that while MetaDORAM2 requires a setup phase with exponential computation, this does not affect its communication complexity. Abraham et al. created an efficient 2-server ORAM using PIR [1]. Their ORAM is Tree-based, in which the number of children of each vertex is a configurable parameter, $b\ge 2$. This protocol achieved a communication cost of $\mathrm{\Theta }({\log }_b(n)d+b\omega (1){\log }_b(n){\log }^2(n))$. The parameter $b$ should be set to reduce the amortized cost. For $d\ge 2\omega (1){\log }^2(n)$ the cost is minimized by setting $b=\frac{d}{\omega (1){\log }^2(n)}$, which results in a cost $\frac{\log (n)}{\log (d)}d$. For smaller $d$, the cost is minimal when $b=2$. Note that while Abraham et al. constructed a 2-server ORAM, converting it to a DORAM while maintaining information-theoretic security requires a third party, to help simulate the virtual client. Chan et al. [10] created an efficient 3-server passive ORAM scheme with perfect security. Their DORAM is Hierarchical, but unlike most Hierarchical ORAMs which use PRFs, Chan et al. store items using truly random position labels. These are stored in a position label ORAM, which is implemented recursively. The communication cost is $\mathrm{\Theta }(\log (n)d+{\log }^3(n))$. Both prior works are multi-server ORAMs with simple clients, which can be converted to 3-party honest-majority DORAMs without increasing the amortized asymptotic communication cost.

Several works also investigated building Distributed Oblivious RAMs directly without simulating a client-server ORAM. While these works generally did not achieve the same asymptotic efficiency as [1] and [10], many had good concrete efficiency. They took advantage of the existence of multiple non-colluding servers by using Distributed Point Functions [8, 39], secret-shared PIR (SSPIR) [24] and secure shuffles/routing [17]. See Table 2 for details. These works all depended on computational assumptions. In comparison, the MetaDORAM protocols are information-theoretically secure. The MetaDORAM protocols also have strictly better asymptotic communication cost than these protocols over all parameter ranges, except for Lu et al. and Falk et al. [31, 17], which can have a lower asymptotic communication cost, and that only when $\kappa +d=o({\log }^2(n)/\log (\log (n)))$.

In this section we provide a broad overview of how the MetaDORAM1 and MetaDORAM2 protocols work. These protocols are, in fact, almost identical and only differ in how hash functions are chosen. Therefore, in this overview, we only discuss the common framework of the solution, which we refer to simply as MetaDORAM. Section 6 later presents MetaDORAM1 and MetaDORAM2 in full detail, including the different approaches used to select hash functions.

At a very high level, MetaDORAM uses Secret-Shared Private Information Retrieval to access items, and always writes the accessed item (whether modified or not) to a pre-determined new location. It uses an oblivious “metadata map” that maintains a mapping from indices to their locations. This is accessed in order to obtain shares of the location to input to the Secret-Shared PIR.

A simple way to instantiate this is to simply store the original secret-shared array in memory, and to always write new items to the next free location in memory. The metadata map would then consist only of the last access time for each index. If the index has been accessed, this uniquely determines the item’s current position; if the index has never been accessed, the position is determined by the index itself. This protocol is simple, but requires performing SSPIR over an array of size $\mathrm{\Omega }(n)$.

In order to perform SSPIR over small arrays, we instead store items in hash tables, each with $h\in \mathrm{\Omega }(\log (n))$ hash functions. As before, items are written to the next free location in memory, but when there are $c$ such items, these too are built into a hash table. To limit the number of hash tables, when there are $b$ tables of a given size, the contents of these tables are extracted and rebuilt into a single table. Let $T_{1,i},\mathrm{\dots },T_{b,i}$ be the tables of the $i^{th}$ smallest size. Furthermore, every $n$ accesses, there is a DORAM refresh in which the contents of all tables are extracted and rebuilt into a single hash table. As a result, there are only ever at most $O({\log }_b(n)b)$ tables, so the SSPIR need only be performed over arrays of size $O(c+b{\log }_b(n)h)=poly(\log (n))$.

Restricting the number of locations accessed improves efficiency, but introduces several security and logistical challenges. Let $G(x)$ be a function returning a 3-D array, such that $G{(x)}_{i,u,k}$ is the $k^{th}$ location accessed in table $T_{i,u}$ when querying $x$.

1. 1.

   The first challenge is that $G(x)$ must leak no information about $x$ (even to a computationally unbounded adversary). This is essential, because the parties who access data during a read will inevitably learn $G(x)$ by the locations they access.

2. 2.

   Additionally, each time $x$ is accessed, $G(x)$ must be a new 3-D array, independent of the previous value(s) of $G(x)$, to avoid leaking that repeated queries occurred. This implies $G(\cdot )$ must be stateful.

3. 3.

   The parties need an efficient protocol for building hash tables which does not leak any correlation between indexes and the locations in which they are stored.

4. 4.

   The SSPIR-index depends not only on the index and the last access time (as in the $\mathrm{\Omega }(n)$-sized SSPIR solution presented above) but also on which of the $h$ hash functions is being used to store the item, which was determined during the hash table build.

It is standard when a hash table satisfies properties (1) and (3) above, that it is called an oblivious hash table. Therefore, throughout all of the hash tables in this work are oblivious hash tables (OHTables).

We solve these by separating the required properties of stateful-updates, randomness and collision-resistance. We set $G{(x)}_{i,u,k}=H_{i,k}(Rand(UniqueNonce(x))$, where:

• $\mathrm{■}$

  $UniqueNonce$ is a stateful function. This function returns a different value for each $x$. Furthermore, each time $x$ is queried by the DORAM, the value of $UniqueNonce(x)$ is updated. This is implemented simply by defining $UniqueNonce(x)=x$ for every $x$ which has not been accessed (since the last DORAM refresh) and defining $UniqueNonce(x)=n+LastAccess(x)$ for each $x$ which has been accessed. (Here $LastAccess(x)\in \{1,\mathrm{\dots },n\}$ is the last time $x$ was accessed, measured from the last DORAM refresh.)

• $\mathrm{■}$

  $Rand$ is a random permutation on $\{1,\mathrm{\dots },2n\}$.

• $\mathrm{■}$

  $H_{i,k}$ are public, fixed hash functions. They are collision-resistant, but do not need to have any other security properties.

We define $Rand(UniqueNonce(x))$ as the rune (Random Unique NoncE) of $x$ (also written $rune(x)$). Note that when $x$ is updated, it will be assigned a new rune.

This solution simultaneously resolves challenges (1) and (2) presented above. $rune(x)$ will be information-theoretic independent of $x$, so $G(x)$ will be as well, solving (1). Since $UniqueNonce(x)$ will return a distinct value each time an index is queried (between each DORAM refresh), and $Rand$ is a permutation, $rune(x)$ will also be a distinct value chosen uniformly at random (without replacement) from $\{1,\mathrm{\dots },2n\}$ for each queried $x$. Therefore, the locations distribution will be independent of the access pattern, and in particular independent of whether indexes are repeated in queries.

To solve challenge (3), we distinguish the roles of the parties. One party, $P_0$, will be the Builder. The other two parties, $P_1$ and $P_2$, will be Holders. The Holders will store the tables and will learn $rune(x)$ when $x$ is queried, allowing them to compute $G(x)$. The Builder picks and stores $Rand$. Observe that when building a new table, the items which are being built have been accessed before, and so $UniqueNonce(x)$ depends only on the last access time of $x$. We write items to secret-shared memory each time they are accessed, according to a fixed schedule. Let $Mem(x)$ represent the location in secret-shared memory of item with index $x$ at a given point in time. The mapping from $Mem(x)$ to $LastAccess(x)$ is therefore public, as is the mapping from $LastAccess(x)$ to $UniqueNonce(x)$. The Builder, knowing $Rand(\cdot )$ therefore also knows the mapping from $Mem(x)$ to $Rand(UniqueNonce(x))=rune(x)$ without knowing $x$. The Builder can therefore locally compute $H_{i,k}(rune(x))$ and locally determines how the memory must be permuted in order to build the oblivious hash table. The Builder then provides this permutation to a secure routing protocol, resulting in a very efficient protocol for constructing oblivious hash tables.

Meanwhile the mapping from $x$ to $rune(x)$ is stored in a smaller DORAM, which we refer to as the sub-DORAM, which is implemented recursively. During an access, this is queried and $rune(x)$ is provided to the Holders, who can use this to calculate $G(x)$, and determine which locations in the oblivious hash tables are to be used for the SSPIR. Note that the Builder knows $Rand$, but does not learn the runes obtained during queries, or the memory locations accessed by the Holders in the tables, so does not learn any information about the access pattern.

We turn to challenge (4). Note that the table, $T_{i,u}$, in which an item is stored is fully determined by the item’s last access time. However, to perform SSPIR, we also need to obtain a secret-sharing of which of the $h$ hash functions was used to store the item in this table. Observe that when the Builder is determining the permutation for building an oblivious hash table, this does not depend on the access pattern, but only depends on $Rand(\cdot )$. Furthermore, the Builder picks $Rand(\cdot )$ at the start of each DORAM refresh. Therefore, the Builder is able to pre-determine the permutations it will use, and therefore which hash function will be used for each rune in each oblivious hash table. This may be surprising, since the mapping from runes to indexes has not even be determined at this point. This is possible because, regardless of which index is accessed at time $t$, the item will be stored in the same initial location in memory, will be assigned the same unique nonce, the same rune, and will be placed in the same locations in each oblivious hash table. This means that the Builder can secret-share a position schedule which determines the SSPIR-index of the rune at each point in time (until the next DORAM refresh).

A final challenge is that SSPIR assumes that the 2 Holders have identical copies of the tables (rather than a secret-sharing of the tables). To provide privacy from the Holders, we therefore mask each item in each table with a rune-dependent information-theoretic mask (one-time pad). During each table rebuild, new masks are applied. This is achieved by the Builder adding (as secret-shares) the masks for the new table, prior to the secure routing protocol. The Builder pre-determines all new masks at the start of each DORAM refresh, and secret-shares a mask schedule among the Holders, akin to the position schedule.

The metadata mapping therefore consists of mappings from indices to runes, from runes to a position schedule and from runes to a mask schedule. The position schedule and mask schedule are simply secret-shared arrays (with the runes public and the schedules secret-shared). The mapping from indices to runes is implemented using a sub-DORAM, which is implemented recursively.

We use lower-case Latin characters to represent parameters in the protocol. $n$ is the size of the RAM, $d$ is the bit-length of each item. $h$ represents the number of hash functions used by the hash tables. For an explicit integer or integral parameter, $a$, $[1,a]$ denotes the set of integers $\{1,\mathrm{\dots },a\}$. We use upper-case Latin characters to represent arrays and matrices, which are indexed using standard subscript notation. $\lg$ represents the base-2 log. For asymptotic annotation, any constant base is equivalent, in which case $\log$ represents some arbitrary constant-base log.

We denote the 3 parties as $P_0$, $P_1$ and $P_2$. $P_0$ is the Builder. $P_1$ and $P_2$ are the Holders. The Adversary $𝒜$, is able to corrupt at most one of the parties. The corruption is semi-honest (passive), that is the corrupted party will still follow the protocol, but $𝒜$ is able to view all data visible to the corrupted party. The corruption is static, that is $𝒜$ cannot change which party is corrupted during the protocol. Our protocols are information-theoretically secure, that is $𝒜$ may perform an arbitrarily large amount of computation.

We utilize hash functions. Our hash functions are fixed and public. The hash functions implicitly map to ranges of different sizes (depending on the size of the OHTable). In this cases, the hash functions are calculated modulo the required range.

We use several kinds of secret-sharing, all of which are bit-wise (Boolean) secret-sharings. These are summarized in Table 3. Since all of these sharings are linear, they can easily be converted between each other. A sharing of an $l$-bit variable can be converted to a fresh sharing of any other $l$-bit variable by each party creating a fresh sharing of their share in the new sharing and XORing the resulting shares. (If 2 parties hold the same share, only one of them need send a sharing.) This requires only $\mathrm{\Theta }(l)$ communication.

The most common sharing we use is a 3-party replicated secret sharing (3RSS) [2]. Here, $x\in {\{0,1\}}^{\mathrm{\ell }}$ is secret-shared by having $x_0,x_1,x_2\in {\{0,1\}}^{\mathrm{\ell }}$ that are uniformly random subject to $x_0\oplus x_1\oplus x_2=x$. $P_i$ holds $x_i$ and $x_{(i+1)mod3}$. When variable $x$ is held using this secret-sharing, it is represented as $[x]$.

We also use a 2-party XOR secret-sharing (2XORS), where 2 parties hold the secret-sharing and the third party is not involved. If $P_1$ and $P_2$ hold a 2-party XOR secret-sharing of variable $x$, this is denoted as ${[x]}_{1,2}$. Here $P_1$ holds $x_0$ and $P_2$ holds $x_1$ where $x_0$ and $x_1$ are randomly chosen subject to $x_0\oplus x_1=x$. We also use a variant of XOR secret-sharing in which 2 parties hold one of the shares, and the third party holds the other. For instance, when $P_0$ holds one share, and $P_1$ and $P_2$ hold the other share, this is denoted ${[x]}_{0,(1,2)}$, that is $P_0$ holds $x_0$ and $P_1$ and $P_2$ both hold $x_1$ where $x_0,x_1\leftarrow {\{0,1\}}^{\mathrm{\ell }}$ subject to $x_0\oplus x_1=x$.

Sometimes a variable is held privately. If $x$ is held privately by one party (1-Priv), for instance, by $P_0$, we denote this as ${[x]}_0$. Sometimes a variable is known to 2 parties but not the third (2-Priv). If $x$ is known to $P_1$ and $P_2$, but not $P_0$, this is denoted ${[x]}_{(1,2)}$.

For conciseness, conversions between types of secret-sharing are typically implicit in our pseudocode, indicated by the sharing-type of the result. For instance, ${[C_j]}_{(1,2)}=[v_{new}]\oplus [e]$ means that $[v_{new}]$ and $[e]$, both stored using 3RSS, are first XORed to create a result that is shared using 3RSS. This result is then revealed to $P_1$ and $P_2$ (but not $P_0$), who store the result and label it $C_j$.

We use the Arithmetic Black Box (ABB) model [14] to formalize the guarantees provided by secret-sharing and operations on secret-shares. This treats 3RSS, 2XORS and 1-2XORS secret-shared values as stored in a reactive functionality ${ℱ}_{ABB}$. ${ℱ}_{ABB}$ can also perform operations on secret-shares (e.g. AND, XOR) with the result again being stored by ${ℱ}_{ABB}$. Only when a ${ℱ}_{ABB}$-stored value is converted to a private (2-Priv or 1-Priv) or public value (corresponding to share reconstruction) is that value released by ${ℱ}_{ABB}$ to the appropriate parties. The protocol of Araki et al. [2] securely implements ${ℱ}_{ABB}$ for any Boolean operation (AND, OR, NOT, XOR) over 3RSS-shared values. Locally XORing shares securely implements ${ℱ}_{ABB}$ for the XOR operation over 2XORS and 1-2XORS sharings.

We wish to implement the following DORAM functionality:

Our definition of a DORAM combines the Read and Write functionalities, allowing for reads, writes, or more complex functionalities. This is done by setting the public function $f$ appropriately. For a read, define $f(v,y)=v$. For a write, define $f(v,y)=y$. Allowing the written value to be a function of the input provides additional flexibility, such as writing to only particular bits of the data-value or applying a bit-mask to the memory value. Implicitly, $f$ must be representable using a Boolean circuit containing $\mathrm{\Theta }(d)$ AND gates.

Security is defined using the simulation paradigm, which is standard for proving the security of MPC protocols [30]. A simulator, given only a party’s inputs and outputs from a protocol must generate a view consistent with the real view of a corrupted party during an execution. The DORAM is perfectly secure if the simulated view is from the same distribution as the real view. It is statistically secure if the distance between the distributions of the views is negligible in $n$. A protocol has information-theoretic security if it has either perfect or statistical security. It is computationally secure if a computationally-bounded adversary has a negligible advantage in distinguishing views in the simulated and real executions. All of our protocols have information-theoretic security. We present two DORAMs, one that is statistically secure and another that is perfectly secure. The only difference between the two protocols is the choice of hash functions: the perfectly secure protocol selects hash functions which allow for the construction of oblivious hash tables on all possible inputs, whereas the statistically secure protocol picks random hash functions which allow for the construction of oblivious hash tables on all possible inputs except with negligible probability. This is the only type of leakage in the statistically secure protocol. Apart from this all components of both protocols are perfectly secure.

Our DORAM implementation makes use of the following functionalities. These can be implemented with perfect security using standard techniques. We present explicit instantiations of the SSPIR and routing functionalities in appendices A and B respectively. The communication cost of SSPIR is $\mathrm{\Theta }(\sqrt{md}+d)$ while that of Route is $\mathrm{\Theta }((d+\log (q))q)$.