Paper 2017/1033

Foundations of Differentially Oblivious Algorithms

T-H. Hubert Chan, Kai-Min Chung, Bruce Maggs, and Elaine Shi


It is well-known that a program's memory access pattern can leak information about its input. To thwart such leakage, most existing works adopt the solution of oblivious RAM (ORAM) simulation. Such a notion has stimulated much debate. Some have argued that the notion of ORAM is too strong, and suffers from a logarithmic lower bound on simulation overhead. Despite encouraging progress in designing efficient ORAM algorithms, it would nonetheless be desirable to avoid the oblivious simulation overhead. Others have argued that obliviousness, without protection of length-leakage, is too weak, and have demonstrated examples where entire databases can be reconstructed merely from length-leakage. Inspired by the elegant notion of differential privacy, we initiate the study of a new notion of access pattern privacy, which we call ``$(\epsilon, \delta)$-differential obliviousness''. We separate the notion of $(\epsilon, \delta)$-differential obliviousness from classical obliviousness by considering several fundamental algorithmic abstractions including sorting small-length keys, merging two sorted lists, and range query data structures (akin to binary search trees). We show that by adopting differential obliviousness with reasonable choices of $\epsilon$ and $\delta$, not only can one circumvent several impossibilities pertaining to the classical obliviousness notion, but also in several cases, obtain meaningful privacy with little overhead relative to the non-private baselines (i.e., having privacy ``almost for free''). On the other hand, we show that for very demanding choices of $\epsilon$ and $\delta$, the same lower bounds for oblivious algorithms would be preserved for $(\epsilon, \delta)$-differential obliviousness.

Available format(s)
Publication info
Published elsewhere. MINOR revision.SODA'19
differential obliviousness
Contact author(s)
runting @ gmail com
2020-08-05: last of 3 revisions
2017-10-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {T-H.  Hubert Chan and Kai-Min Chung and Bruce Maggs and Elaine Shi},
      title = {Foundations of Differentially Oblivious Algorithms},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1033},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.