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.