Paper 2018/1051

Lower Bounds for Differentially Private RAMs

Giuseppe Persiano and 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 learn global properties. For the case of outsourced databases, the adversary also views the patterns of access to data. Oblivious RAM (ORAM) can be used to hide access patterns but ORAM might be excessive as in some settings it could be sufficient to be compatible with differential privacy and only protect the privacy of individual accesses. We consider $(\epsilon, \delta)$-Differentially Private RAM, a weakening of ORAM that only protects individual operations and seems better suited for use in data analysis on outsourced databases. As differentially private RAM has weaker security than ORAM, there is hope that we can bypass the $\Omega(\log(n/c))$ bandwidth lower bounds for ORAM by Larsen and Nielsen [CRYPTO ’18] for storing an array of $n$ entries and a client with $c$ bits of memory. We answer in the negative and present an $\Omega(\log(n/c))$ bandwidth lower bound for privacy budgets of $\epsilon = O(1)$ and $\delta \le 1/3$. The information transfer technique used for ORAM lower bounds does not seem adaptable for use with the weaker security guarantees of differential privacy. Instead, we prove our lower bounds by adapting the chronogram technique to our setting. To our knowledge, this is the first work that uses the chronogram technique for lower bounds on privacy-preserving storage primitives.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
oblivious RAMdifferential privacylower bounds
Contact author(s)
kwlyeo @ google com
2018-11-02: received
Short URL
Creative Commons Attribution


      author = {Giuseppe Persiano and Kevin Yeo},
      title = {Lower Bounds for Differentially Private RAMs},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1051},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.