In recent years, there has been significant work in studying data structures that provide privacy for the operations that are executed. These primitives aim to guarantee that observable access patterns to physical memory do not reveal substantial information about the queries and updates executed on the data structure.

The concept of an Oblivious RAMs (ORAMs) has been introduced by Goldreich and Ostrovsky [6]. An ORAM can be viewed an a secure implementation of the simplest data structure: an array (or a RAM) whose entries can be read and over-written. The typical setting is that of a client that has limited memory and outsources the storage of the array to a remote server and accesses the data stored in the array over a network. Clearly, to protect the confidentiality of the data, each entry can be encrypted before the upload and decrypted once it is downloaded. Still, the server sees the access pattern and from this deduce the type of algorithm that is being executed which in turn can reveal the interest of the client. An ORAM is a protocol between the client and server that hides the access pattern. The obliviousness guarantee of an Oblivious RAM requires that no adversary that picks two challenge sequences of operations of the same length and observes the access pattern incurred by the execution of one of the sequences still cannot determine which of the two sequences gave rise to the access pattern observed.

In recent years, ORAMs have been studied extensively to try and determine the optimal overhead (see [3, 6, 7, 9, 11] and references therein) that was reduced from \(O(\log ^3n)\) to \(O(\log n)\), for a RAM with n entries. Indeed, for b-bit entries on a server with memory cell (word) size of \(\omega =\varTheta (b)\) bits, the best known construction obtains logarithmic overhead \(O(b/\omega \cdot \log n)\) [1] and requires only constant client memory.

Is this the best we can do?

The first logarithmic lower bounds were proven by Goldreich and Ostrovsky [6] of the form \(\varOmega ((b/\omega ) \cdot (\log n/\log c))\) where the client has storage of c bits. Boyle and Naor [2] pointed out that these lower bounds assumed the so-called balls-and-bins model with a non-encoding assumption on the underlying blocks. Larsen and Nielsen [10] were the first to prove lower bounds for the general case; i.e., without making any encoding assumption. They proved that a RAM of n entries each of b bits implemented by a server with a memory consisting of \(\omega \)-bit words and a client with c bits of local memory requires \(\varOmega ( (b/\omega ) \cdot \log (nb/c))\). This bound becomes increasingly weak as \(\omega \) grows and Komargodski and Lin [8] proved a lower bound of \(\varOmega (\log (nb/c) / \log (\omega /b))\) for the case \(\omega >b\).

In the hope of obtaining faster RAM that would still offer an adequate level of security, researchers have looked at weaker but still meaningful notions of security. In this talk we will overview three attempts and show that indeed any meaningful notion of security for RAMs seems to be as hard as Obliviousness.

Differentially Private RAMs. In various practical applications, including the field of privacy-preserving data analysis, the notion of Differential Privacy [5] is considered to offer an adequate level of protection. Differentially Private RAMs (DPRAMs) aim to provide privacy for individual operations, but may reveal information about a sequence consisting of many operations. In more detail, if an adversary receives two candidate equal-length operational sequences that differ in one operation and the access pattern incurred by the execution of one of the two sequences, the adversary should not be able to guess the identity of the executed sequence with too high probability. Unfortunately, DPRAMs incur in the same overhead as ORAM. Specifically, the \(\varOmega (b/\omega \cdot \log {nb/c})\) lower bound for DPRAMs by Persiano and Yeo [15] showed that this is impossible when \(b = \varOmega (\omega )\) and, recently, this has been extended to \(\varOmega (\log (nb/c) / \log (\omega /b))\) which is significant for the case \(\omega >b\) by [16].

Leaky RAMs. A second approach allows the RAM to leak some partial information about the sequence of operations. Currently, all known leaky RAMs with constant overhead reveal if two operations are performed on the same key or not. We denote this as \( global\ key{-}equality\ pattern \). The result of [12] gives strong evidence that the leakage of the global key-equality pattern is inherent for any leaky RAM construction with O(1) efficiency. In particular, they consider the slightly smaller leakage of decoupled key-equality pattern where leakage of key-equality between update and query operations is decoupled and the adversary only learns whether two operations of the \( same\ type \) are performed on the same key or not. They show that any leaky RAM with at most decoupled key-equality pattern leakage incurs \(\varOmega (b/w\cdot \log n)\) overhead.

Snapshot Adversaries. In some applications the server executing the access is not trusted but it could be temporarily compromised by an external adversary. Very recently, Du, Genkin and Grubbs [4] presented an ORAM construction with \(O(\log \ell )\) overhead protecting against a snapshot adversary that observes the transcript of \(\ell \) consecutive operations from a single breach. For small values of \(\ell \), this outperforms standard ORAMs. However, if one allows to have 3 breaches, it has been recently proved [14] that we go back to \(\varOmega (b/w\cdot \log (nb/c))\) overhead.

Open Problem. The following question is thus still open. Is there a meaningful notion of security for which RAMs require a sub-logarithmic, or maybe even constant, overhead?

Also, it would be interesting to look at different data structures. The research reported in [16] has a general framework to prove lower bounds for more sophisticated data structures.