Kasper Green Larsen, Jesper Buus Nielsen

An Oblivious RAM (ORAM) introduced by Goldreich and Ostrovsky

[JACM'96] is a (possibly randomized) RAM, for which the memory access

pattern reveals no information about the operations

performed. The main performance metric of an ORAM is the bandwidth

overhead, i.e., the multiplicative factor extra memory blocks that must be

accessed ...
more >>>

Giuseppe Persiano, Kevin Yeo

In this work, we study privacy-preserving storage primitives that are suitable for use in data analysis on outsourced databases within the differential privacy framework. The goal in differentially private data analysis is to disclose global properties of a group without compromising any individualâ€™s privacy. Typically, differentially private adversaries only ever ... more >>>

Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo

We prove an $\Omega(d \lg n/ (\lg\lg n)^2)$ lower bound on the dynamic cell-probe complexity of statistically $\mathit{oblivious}$ approximate-near-neighbor search (ANN) over the $d$-dimensional Hamming cube. For the natural setting of $d = \Theta(\log n)$, our result implies an $\tilde{\Omega}(\lg^2 n)$ lower bound, which is a quadratic improvement over the ... more >>>

Daniel Noble, Brett Hemenway, Rafail Ostrovsky

This paper presents the first Distributed Oblivious RAM (DORAM) protocol that achieves sub-logarithmic communication overhead without computational assumptions.

That is, given $n$ $d$-bit memory locations, we present an information-theoretically secure protocol which requires $o(d \cdot \log(n))$ bits of communication per access (when $d = \Omega(\log^2(n)$).

This comes as a surprise, ... more >>>