Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Oblivious RAM:
TR18-109 | 29th May 2018
Kasper Green Larsen, Jesper Buus Nielsen

Yes, There is an Oblivious RAM Lower Bound!

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

TR18-181 | 30th October 2018
Giuseppe Persiano, Kevin Yeo

Lower Bounds for Differentially Private RAMs

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

TR19-055 | 9th April 2019
Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo

Lower Bounds for Oblivious Near-Neighbor Search

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

TR24-005 | 4th January 2024
Daniel Noble, Brett Hemenway, Rafail Ostrovsky

MetaDORAM: Breaking the Log-Overhead Information Theoretic Barrier

Revisions: 1

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

ISSN 1433-8092 | Imprint