Oblivious Parallel RAM: Improved Efficiency and Generic Constructions | Springer Nature Link

A Correctness and Obliviousness of ORAM

For an access sequence \({\varvec{y}}\) we let \(\mathsf{AP}_i = \mathsf{AP}_i({\varvec{y}})\) be the access pattern of its i-th operation – i.e., the sequence of pairs \((\overline{{\text {op}}}_{i, 1}, \overline{a}_{i, 1}), \ldots , (\overline{{\text {op}}}_{i, q_i}, \overline{a}_{i, q_i})\) describing the client’s server accesses (without the actual values) when processing the i-th operation – and denote by \(\mathrm {val}_i\) the answer of this operation. Then, we let

We say that the sequence of outputs \({\varvec{z}} = \mathsf {Out}_\mathcal {O}(\lambda , N, B,{\varvec{y}})\) of \(\mathcal {O}\) is correct w.r.t. the sequence of logical accesses \({\varvec{y}}\), if for each logical command \(\mathsf{Acc}({\text {op}}_i, \mathsf {a}_i, v_i)\) in \({\varvec{y}}\), the corresponding output \(\mathrm {val}_i\) in \({\varvec{z}}\) is either the most recently written value on address \(\mathsf {a}_i\), or \(\bot \) if \(\mathsf {a}_i\) has not yet been written to. Let \(\mathsf{Correct}\) be the predicate that on input \(({\varvec{y}}, {\varvec{z}})\) returns whether \({\varvec{z}}\) is correct w.r.t. \({\varvec{y}}\).

Definition 2

(ORAM Correctness and Security). An ORAM \(\mathcal {O}\) achieves correctness and obliviousness if for all \(N, T, B = {poly}(\lambda )\), there exists a negligible function \(\mu \), such that, for every \(\lambda \), every two sequences \({\varvec{y}}\) and \({\varvec{y}}'\) of \(T(\lambda )\) access operations, the following are satisfied:

1. 1.

   Correctness: \(\Pr \left[ \mathsf{Correct}\left( {\varvec{y}}, \mathsf {Out}_\mathcal {O}(\lambda , N, B,{\varvec{y}}) \right) = 1\right] \ge 1-\mu (\lambda )\).

2. 2.

   Obliviousness: \(\varDelta \left( \mathsf{AP}_\mathcal {O}(\lambda , N, B,{\varvec{y}}), \mathsf{AP}_\mathcal {O}(\lambda , N, B,{\varvec{y'}}) \right) \le \mu (\lambda )\).

We note that the above definition considers statistical obliviousness. This is generally achieved by tree-based ORAM schemes, but it can be relaxed to computational obliviousness, where the statistical distance is replaced by the best distinguishing advantage of a PPT distinguisher.

B Review of Path-ORAM

In this section, we review the Path-ORAM scheme in detail, as it is used as a starting point for Subtree-ORAM and Subtree-OPRAM.

Overview. Path-ORAM is a tree-based ORAM that works for the single client setting. To implement a logical storage space for N data blocks, Path-ORAM organizes the storage space (virtually) as a complete binary tree with depth \(D = \lceil \log N \rceil \). Each node of the tree is a bucket capable of storing Z blocks of size B (bits). Here Z is a constant, thus the server storage overhead is O(1). To hide the logical access patterns, each data block \(\mathsf {a}\) is assigned to a random path \(\ell \) from root to leaf in the tree and stored at some node of the path; in order to hide the repetitive accesses to the same block, the assignment is updated to a new independent random path after each access.

In [26], Path-ORAM is constructed in two steps; first, a non-recursive version is proposed and analyzed, in which the client keeps a local position map with \(N\log N\) bits; then the position map is recursively outsourced to the server, reducing the client storage to only \({{\mathrm{polylog}}}(N)\) bits. Below we describe the non-recursive version first, and then show how to apply the recursive transformation.

Non-Recursive Version. The client maintains a position map that maps each block \(\mathsf {a}\) to a path \(\mathsf{pos.map}(\mathsf {a})\). Since each path can be specified using D (the depth of the tree) bits, the size of the position map is \(ND = N \lceil \log N \rceil \) bits. Additionally, the client keeps a small local storage stash used for storing blocks that do not fit in the assigned path (due to limited space at each tree node). The capacity of the stash is bounded by \(R = R(\lambda )\) for any function \(R(\lambda ) = \omega (\log \lambda )\), except with negligible probability in \(\lambda \).

Given the i-th logical access \(\mathsf{Acc}(op_i, \mathsf {a}_i, v_i)\), Path-ORAM proceeds in two phases:

• Phase 1: Processing the query. Path-ORAM retrieves the path \(\ell _i = \mathsf{pos.map}(\mathsf {a}_i)\) assigned to block \(\mathsf {a}_i\), and finds the block \(\mathsf {a}_i\) on the path or in the stash. After returning the block value and potentially updating the block, Path-ORAM re-assigns block \(\mathsf {a}\) to a new independent random path \(\ell ' \displaystyle \mathop {\leftarrow }^{\$}[N]\) and updates \(\mathsf{pos.map}(\mathsf {a}_i)=\ell '_i\). It then moves the block to the stash.

• Phase 2: Flushing and write-back. Before re-encrypting and writing the path back to the server, in order to avoid the stash from “overflowing”, Path-ORAM re-arranges path \(\ell _i\), to fit as many blocks from the stash into the path. More specifically, for each block \(\mathsf {a}_j\) in the stash and on the path, Path-ORAM places it at the lowest non-full node \(p_j\) that intersects with its assigned path \(\ell _j = \mathsf{pos.map}(\mathsf {a}_j)\). If no such node is found, the block remains in the stash. If at any point, the stash contains more than R blocks, Path-ORAM outputs “overflow” and aborts.

Recursive Version. In the above non-recursive version, the client keeps a large \(N \log N\)-bit position map. To reduce the client storage, Path-ORAM recursively outsources the position map to the server by adding extra \(O(\log N)\) trees. More specifically, if the cell size \(B \ge \alpha \lceil \log N \rceil \) for some integer \(\alpha > 1\), the position map can be stored in \(\lceil \frac{N}{\alpha } \rceil \) cells. This means, to answer an access to a logical storage space of size N, the non-recursive version only needs to make a query to another logical storage space (i.e. the position map) of size \(\lceil \frac{N}{\alpha } \rceil \). Therefore, if the client further outsources the position map to the server, its local storage would be reduced to \(\lceil \frac{N}{\alpha ^2} \rceil \). This idea can be applied recursively until the client storage becomes \({{\mathrm{polylog}}}(N)\). In the final scheme, at the server, besides tree \(\mathcal{T}_0\) that stores data blocks, there are additional trees \(r\mathcal{T}_1, r\mathcal{T}_2, ..., r\mathcal{T}_l\) for position map queries, where \(l = \lceil \log _{\alpha }N \rceil \). Tree \(r\mathcal{T}_i\) has size \(\tilde{O}(\lceil \frac{N}{\alpha ^i} \rceil B)\) bits, and maintains the position map corresponding to tree \(r\mathcal{T}_{i-1}\) which contains \(\lceil \frac{N}{\alpha ^{i-1}} \rceil \) cells. The position map corresponding to tree \(r\mathcal{T}_l\) is stored in local storage. Now, to access a block \(\mathsf {a}\), the client needs to query \(\mathsf{pos.map}(\mathsf {a})\) in \(\mathcal{T}_0\) by looking up the position in tree \(r\mathcal{T}_1\). In order to query the position map corresponding to tree \(r\mathcal{T}_1\), similarly, the client looks up in \(r\mathcal{T}_2\), so on and so forth. Finally the position map value of tree \(r\mathcal{T}_l\) is stored in local storage.

Complexity. The storage overhead is O(1) both in the non-recursive version and the recursive version. In the non-recursive version, for each logical access, Path-ORAM reads and writes a path with \(\log N\) nodes, each of which contains Z cells, therefore the communication overhead is \(O(\log N)\) per access. The computation overhead is \(O(\log ^2 N)\), since the flushing procedure takes time \(O(\log ^2 N)\) per access. After the recursive transformation is applied, to answer each logical access, the client needs to query \(l = \lceil \log _{\alpha }N \rceil \) number of trees, and hence the communication/computation overhead blow by a factor of \(\log N\).

C Analysis of Subtree-ORAM

In the full version, we show that the overflow probability of Subtree-ORAM is negligible given any sequence of logical access requests. In particular, we prove the following proposition, which generalizes the analysis of Path-ORAM.

Proposition 1

Fix the stash size to any \(R(\lambda ) \in \omega (\log \lambda )\). For every polynomial m, N, T, B, there exists a negligible function \(\mu \), such that, for every \(\lambda \), and sequence \({\varvec{y}}\) of T batches of m access requests, the probability that Subtree-ORAM outputs \(\mathsf{overflow}\) is at most \(\mu (\lambda )\).

From Proposition 1, it is easy to show that Subtree-ORAM satisfies correctness and obliviousness.

• Correctness: Since the stash overflows with negligible probability, and Subtree-ORAM maintains the block-path invariance (as in Path-ORAM) – at any moment, each block can be found either on the path currently assigned to it or in the stash; by construction, Subtree-ORAM answers logical accesses correctly according to the correctness condition of ORAM.

• Obliviousness: Conditioned on no overflowing: (1) In each iteration, Subtree-ORAM always reads m independent and random paths from the server. (2) After each iteration, every requested block is assigned to a new random path, which is hidden from the adversary (as in Path-ORAM). Thus the construction is oblivious.

D Analysis of Subtree-OPRAM

In this section, we give a high-level overview of why Subtree-OPRAM is correct and satisfies obliviousness. Also we discuss below the complexity of the protocol.

We discuss correctness and obliviousness for the non-recursive version only. The same properties are then also easily shown to be true for the recursive version. The first key observation is that the m clients of Subtree-OPRAM can be seen as collectively emulating the operations of the single client of Subtree-ORAM. Compare an execution of Subtree-OPRAM with a sequence \({\varvec{y}}\) of T batches of m parallel logical accesses with the execution of Subtree-ORAM with the same sequence.^{Footnote 9} Then, we observe the following:

1. 1.

   The ORAM tree \(\mathcal{T}\) of Subtree-ORAM is stored in parts in Subtree-OPRAM: All but the top \(\log m\) levels is stored as the m-tree forest \(\mathcal{T}_1, \cdots , \mathcal{T}_m\) at the server, while the top \(\log m\) levels are stored in a distributed way by the individual clients in their respective stashes — namely, if a block is stored at client j, its assigned path belongs to \(\mathcal{T}_j\). Therefore, the union of \(\left\{ \mathsf{stash}_i \right\} \) contains the same blocks as the stash of Subtree-ORAM, as well as all blocks in the top of the tree \(\mathcal{T}\) of Subtree-ORAM.

2. 2.

   Subtree-OPRAM answers a batch of m requests (in each iteration) as Subtree-ORAM does: The m clients of Subtree-OPRAM choose a representative for each requested block (in Step 1) with the exactly same rule Subtree-ORAM uses to remove repetitive accesses, and to only keep one access per block. Later (in Step 4), Subtree-OPRAM first answers requests using the most recently written value from previous iterations and then executes the write operations; in particular, due to the way representatives are chosen, the write operation with the minimal index always takes effect.

3. 3.

   Subtree-OPRAM maintains the block-path invariant as Subtree-ORAM. This is because each time a block is assigned to a new path \(\ell '\), it is sent (using the \(\mathsf {OblivRoute}\) sub-protocol) to client j managing the tree \(\mathcal{T}_j\) the path \(\ell '\) belongs to. Therefore, at any moment, a block is either on its assigned path or in the local stash of the client responsible for the tree its assigned path belongs to.

4. 4.

   Subtree-OPRAM emulates the flushing procedure of Subtree-ORAM: Recall that Subtree-ORAM flushes along the subtree \(\mathcal{T}_{\mathrm {real}}\) of paths assigned to all requested blocks. Removing the top \(\log m\) levels of \(\mathcal{T}_{\mathrm {real}}\) gives a set of m subtrees \(\mathcal{T}_{{\mathrm {real}}_1}, \cdots , \mathcal{T}_{{\mathrm {real}}_m}\). Note that \(\mathcal{T}_{{\mathrm {real}}_i}\) is exactly the subtree that client i in Subtree-OPRAM performs flushing on (in Step 6). Indeed, by the design of the subtree flushing procedure, blocks that land in different subtrees \(\mathcal{T}_{\mathrm {real}_i} \ne \mathcal{T}_{\mathrm {real}_j}\) can be operated on independently. Moreover, blocks that would land in the top \(\log m\) levels of \(\mathcal{T}_{\mathrm {real}}\) or stash in Subtree-ORAM are naturally divided into the m local stashes according to which tree \(\mathcal{T}_j\) their assigned path belongs to.

Correctness and Stash Analysis. By the above, if we fix any sequence \({\varvec{y}}\) of parallel accesses, and consider the executions of (non-recursive) Subtree-OPRAM and (non-recursive) Subtree-ORAM with the same input sequence \({\varvec{y}}\), since Subtree-ORAM answers every request correctly as long as it does not overflow, so does Subtree-OPRAM.

To argue that Subtree-OPRAM only overflows with negligible probability, recall that by Proposition 1, when the stash size of Subtree-ORAM is set to any \(R'(\lambda ) \in \omega (\log (\lambda ))\), the probability of overflowing is negligible. We can thus bound the size of each local stash \(\mathsf{stash}_i\) in Subtree-OPRAM, using the bound on the stash size of Subtree-ORAM. As noted above, after each iteration, the local stash \(\mathsf{stash}_i\) of client i stores two types of blocks:

1. 1.

   Blocks in the stash of Subtree-ORAM with an assigned path belonging to \(\mathcal{T}_i\), and

2. 2.

   Blocks in the top \(\log m\) levels of the ORAM tree \(\mathcal{T}\) of Subtree-ORAM, again with an assigned path belonging to \(\mathcal{T}_i\).

By Proposition 1, the number of blocks of the first type is bounded by \(\omega (\log \lambda )\) with overwhelming probability. Moreover, it is easy to see that the number of blocks of the second type is bounded by \(O(\log m)\). Therefore, the size of \(\mathsf{stash}_i\) is bounded by any \(R(\lambda , m) \in \omega (\log \lambda ) + O(\log m)\) with overwhelming probability. This is summarized by the following lemma.

Lemma 1

Fix the stash size to any \(R(\lambda , m) \in \omega (\log \lambda ) + O(\log m)\). For every polynomial m, N, T, B, there is a negligible function \(\mu \), such that, for every \(\lambda \), and sequence \({\varvec{y}}\) of \(T(\lambda )\) accesses, the probability that any client of the non-recursive Subtree-OPRAM outputs \(\mathsf{overflow}\) is at most \(\mu (\lambda )\).

Complexity. The storage overhead of Subtree-OPRAM is the same as that of Path-ORAM, which is O(1). The only contents stored at each client are the stashes, one per recursion level. Since each stash is of size \(R(\lambda , m)B\), and the recursion depth is bounded by \(O(\log N)\), the total client storage overhead is \(O(\log N)R(\lambda , m) \in \omega (\log N\log \lambda )+ O(\log N\log m)\).

Next, we analyze the communication and computation overheads (per client per access) of the recursive Subtree-OPRAM. In each iteration, to process m logical accesses (one per client), the m clients first recursively look up the position maps for \(O(\log N)\) times using the non-recursive Subtree-OPRAM, and then process their requests using again the non-recursive Subtree-OPRAM. Fix any client i, we analyze its communication and computation complexities as follows:

• Server communication overhead: In each invocation of non-recursive Subtree-OPRAM, client i reads/writes a subtree of paths delegated to it by other clients. Since these paths are all chosen at random, in expectation client i read/write only 1 path in each invocation. Furthermore, across all \(O(\log N)\) invocations of non-recursive Subtree-OPRAM, the probability that client i is delegated to read/write \(\omega (\log \lambda ) + O(\log N)\) paths is negligible. (Consider tossing \(O(\log N)\times m\) balls (read/write path requests) randomly into m bins (clients); the probability that any bin has more than \(O(\log N) + \omega (\log \lambda )\) balls is negligible in \(\lambda \).) Since each path contains \(O(\log N)\) blocks, the server communication overhead is bounded by \(\omega (\log \lambda \log N) + O(\log ^2 N) \) in the worst case, with overwhelming probability.

• Inter-client communication overhead: In each invocation of the non-recursive Subtree-OPRAM protocol, client i communicates with other clients in two ways: (1) using the oblivious sub-protocols (Steps 1, 4 and 5) and (2) sending the requests for reading certain block and path \((i, \mathsf {a}'_i, \ell _i)\) (Step 2) and sending back the retrieved block (Step 3). The maximum communicating complexity of the oblivious sub-protocols is \(O(K\log m(\log m + \log N + B))\) bits, where K is in \(\omega (\log \lambda )\). Therefore, across \(O(\log N)\) invocations of non-recursive Subtree-OPRAM, the first type of inter-client communication involves sending/receiving at most \(O(\log N K \log m(\log m + \log N + B))\) bits. On the other hand, by a similar argument as above, across \(O(\log N)\) recursive invocations, with overwhelming probability, each client receives at most \(O(\log N) + \omega (\log \lambda )\) requests of form \((i, \mathsf {a}'_i, \ell _i)\), and hence the second type of communication involves sending/receiving \((\omega (\log \lambda ) + O(\log N))\times O(\log m + \log N +B)\) bits with overwhelming probability. Thus, in total, the inter-client communication is \(\omega (\log \lambda )\log m \log N (\log m + \log N + B)\) bits. Since \(B \ge \alpha \log N\) for an \(\alpha > 1\), the inter-client communication overhead is \(\omega (\log \lambda )\log m (\log m + \log N)\).

Finally, we observe that when considering the communication overhead averaged over a sufficiently large number T of parallel accesses, the server communication overhead is bounded by \(O(\log ^2 N)\) with overwhelming probability. The inter-client communication complexity stays the same.

Obliviousness. The obliviousness of recursive Subtree-OPRAM follows from that of the non-recursive version. Conditioned on that the stash does not overflow, the latter follows from three observations: (i) In each iteration, the paths \(\left\{ \ell _i \right\} \) read/write from/to the server (in Steps 3 and 6) are all independent and random, (ii) the communication between different clients is either through one of the oblivious sub-protocols (in Steps 1, 4, and 5), which has fixed communication pattern, or depends on the random paths \(\left\{ \ell _i \right\} \) (in Steps 2 and 3), and (iii) the new assignment of paths \(\left\{ \ell '_i \right\} \) to blocks accessed are hidden using \(\mathsf {OblivRoute}\) (in Step 5). Combining these observations, we conclude that the access and communication patterns of Subtree-OPRAM is oblivious of the logical access pattern.

E Analysis of Generic-OPRAM

Recursive Version. The above protocol assumes that every client has (private) access to the partition map to be accessed and updated throughout the execution of the protocol. This is of course not realistic. But similar to the case of the position map in Subtree-OPRAM, we can use \(O(\log N)\)-deep recursion. For this to work, we need block size to be at least, say, \(B = 2\log m\), since each entry in the partition map can be represented by \(\log m\) bits.

Complexity Analysis. We now analyze the complexity of the Generic-OPRAM. We assume that \(\mathcal {OD}_i\) is implemented from some ORAM scheme \(\mathcal {O}_i\) which has communication overhead \(\alpha (N')\) when using address space \(N'\), and that the same scheme stores \(M(N')\) blocks on the server for the same address space. We make some assumptions in the following that appear reasonable, namely that \(\alpha (O(N')) = O(\alpha (N'))\) and \(M(O(N')) = O(M(N'))\) (this is true because these functions are polynomial). Moreover, we can also assume also that \(M(N'/c) \le M(N')/c\) for any constant c. (Note that the scheme is meaningful without these assumptions, but the resulting complexity statement would be somewhat more cumbersome.)

• Server and Client Storage. Let us start with the non-recursive case. Note that each partition needs enough blocks to implement a dynamic data structure to store \(2N/m + R\) blocks. This will require an ORAM for \(N' = O(N/m + R)\) blocks, which thus requires \(O(M(N/m + R))\) blocks. Thus, the overall server storage complexity is of \(O(m \cdot M(N/m + R))\) blocks. If \(M(N') = O(N')\), in particular this implies that the overall storage complexity is \(O(N + m R)\), and thus linear if \(m \cdot R \in O(N)\).

  For the recursive case, note that the storage space is going to at least halve after each recursion level by our assumption on M. So if we assume that \(N/m > R\), we see that the storage complexity remains \(O(m \cdot M(N/m + R))\). Every client needs to store R blocks, and moreover, it needs \({{\mathrm{polylog}}}(N)\) memory for implementing \(\mathcal {OD}\) and the underlying ORAM scheme \(\mathcal {O}\), which we assume to have \({{\mathrm{polylog}}}(N)\) client storage overhead.

• Server Communication. In contrast to Subtree-OPRAM above, a generic construction does not necessarily allow us to parallelize accesses to the data structure. The number of \( \mathcal {OD}_{i}(\mathcal {R} \& \mathcal {D}, \cdot )\) operations a client performs can thus vary in each round, but we can apply the same analysis as for Subtree-OPRAM above. Namely, given we are using \(\log N\) levels of recursion, the per-client server communication is \(O(\log N \cdot \alpha (N/m + R))\) in the amortized case, and \(O((\log N + \omega (\log \lambda )) \cdot \alpha (N/m + R))\) in the worst case.

• Inter-Client Communication. The analysis is the same as the one for Subtree-OPRAM.

Correctness. We analyze our scheme and show that it is indeed a valid OPRAM scheme.

Lemma 2

Generic-OPRAM satisfies correctness, and in particular only overflows with negligible probability, as long as \(\mathcal {OD}\) is also correct and only fails with negligible probability.

We omit part of the correctness proof, and restrict ourselves to the more involved part of the analysis, proving that none of the stashes \(\mathsf {SS}_i\) ever overflows, and that none of the partition is supposed to hold more than \(2N/m + R\) elements. Conditioned on no overflows, correctness can then be verified by inspection.

The final result on the overflow probability summarized by the following lemma.

Lemma 3

For every constant \(\kappa \ge 2\), every \(T = T(\lambda )\), and every logical access sequence \({\varvec{y}}\) of T batches of m parallel logical instructions,

where the randomness is taken over the partition assignment, and the constant in the exponent depends on \(\kappa \) only.

We split the proof of the lemma into two propositions – the first pertaining to \(\mathsf{{SS}_i}\) overflowing, the second to partition load. We stress that the proof first proposition relies on some interesting (and non-elementary) fact from basic queueing theory to ensure that a constant outflow of (at most) two blocks is sufficient to avoid an overflow.

Proposition 2

For every constant \(\kappa \ge 2\), every \(T = T(\lambda )\), and every logical access sequence \({\varvec{y}}\) of T batches of m logical instructions,

where the randomness is taken over the partition assignment, and the constant in the exponent depends on \(\kappa \) only.

Proof

We prove the lemma for \(\kappa = 2\). It will be clear that the bound only improve for larger \(\kappa > 2\). Let us look at what happens with one particular stash \(\mathsf {SS}_i\) for some \(i \in [m]\) over time, and compute the probability that it ever contains more than R elements. We model this via the following process:

• Single-bin process: In each iteration, m balls are thrown into one out of m bins independently, and each one lands in the single bin we are looking at with probability 1 / m. Then, \(\kappa = 2\) balls are taken out of the bin (if the bin contains at least \(\kappa = 2\) balls), and otherwise the bin is emptied.

Note that in the actual protocol execution, less than m balls may be thrown into bins at each round because of possible repetition patterns, but it is clear that by always assuming that up to potential m balls can be thrown in the bin can only increase the probability of overflowing, and thus this will be assumed without loss of generality.

To analyze the probability that the bin overflows at some point in time (i.e., it contains more than R balls), we use the stochastic process proposed in Example 23 of [22], with \(a=0, b=+\infty \). There, it is shown that the number of balls in the bin at iteration T is distributed as the random variable

where \(Z_0 = 0\) and

with \(V_j\) denoting the number of balls going to the bin in iteration j and \(U_j\) denoting the potential number of balls taken out from the bin in iteration j. Here \(U_j = 2\) for every j, thus

where \(T_i = \sum _{j \le i} V_j\). Note that \(V_j\) can be seen as the sum of m independent Bernoulli random variables, each being one with probability 1 / m. Therefore, \(T_i\) is the sum of \(m \cdot i\) Bernoulli random variables with expected value i. We want to show now that with very high probability, \(T_i \le 2i + R\). We can simply use the Chernoff bound, and consider two cases. First, if \(R/i \ge 1\), then

where \(\varepsilon = R/i\). Note that

Thus \(\Pr \left[ T_i \ge 2i + R\right] \le e^{-R/3}\). The second case is that \(R/i \le 1\). Then,

Therefore, by the union bound, the probability that there exists some i such that \(Z_i \ge R\) is at most \(T \cdot e^{-R/3}\), i.e., \(X_{T} \le R\), except with probability \(T \cdot e^{-R/3}\). To conclude, once again by the union bound, we obtain the bound on the probability that one of the m stashes overflows. \(\quad \square \)

We also need to analyze the probability that too many elements are assigned to one partition, as otherwise our protocol would also fail.

Lemma 4

For a given partition map \(\mathsf {partition}: [N] \rightarrow [m]\), denote by L the maximum numbers of addresses \(\mathsf {a}\in [N]\) assigned to the same partition p. Then, for any sequence of T batches of m operations and any \(R \ge 2\), the probability that any point in time, \(L \ge 2N/m + R\) ist at most \(T \cdot m \cdot e^{-R/2}\).

Proof

Take the partition map contents at some fixed point in time, and fix some partition \(i \in [m]\). The entire contants of the partition map are N independent random variables, and each one of them is equal to i with probability 1 / m. Let \(L^i\) be the number of addresses assigned to this given i, and let \(L = \max _{i} L^i\). Note that \(L^i\) is a sum of Bernoulli random variables with expectation N / m. We can then use the Chernoff bound to see that

for \(\varepsilon = R m / N\). By the union bound,

And finally, note that there are at most T different “assignments” of position maps due to the structure of the protocol, and thus the overall bound on the probability follows – once again – by the union bound. \(\quad \square \)

Obliviousness. Generic-OPRAM also satisfies the obliviousness property. The formal proof (which we omit) relies on the obliviousness of the \(\mathcal {OD}_i\)’s and the fact that whenever processing a batch of m logical accesses, the above scheme accesses first m randomly chosen partitions, and moreover, in the second phase, each partition is accessed exactly twice.