Paper 2017/1033

Foundations of Differentially Oblivious Algorithms

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

Abstract

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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. MINOR revision.SODA'19
Keywords
differential obliviousness
Contact author(s)
runting @ gmail com
History
2020-08-05: last of 3 revisions
2017-10-28: received
See all versions
Short URL
https://ia.cr/2017/1033
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1033,
      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{https://eprint.iacr.org/2017/1033}},
      url = {https://eprint.iacr.org/2017/1033}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.