Paper 2022/1357

A Theory of Composition for Differential Obliviousness

Mingxun Zhou, Carnegie Mellon University
Elaine Shi, Carnegie Mellon University
T-H. Hubert Chan, University of Hong Kong
Shir Maimon, Cornell University

Differential obliviousness (DO) access pattern privacy is a privacy notion which guarantees that the access patterns of a program satisfy differential privacy. Differential obliviousness was studied in a sequence of recent works as a relaxation of full obliviousness. Earlier works showed that DO not only allows us to circumvent the logarithmic-overhead barrier of fully oblivious algorithms, in many cases, it also allows us to achieve polynomial speedup over full obliviousness, since it avoids "padding to the worst-case" behavior of fully oblivious algorithms. Despite the promises of differential obliviousness (DO), a significant barrier that hinders its broad application is the lack of composability. In particular, when we apply one DO algorithm to the output of another DO algorithm, the composed algorithm may no longer be DO (with reasonable parameters). More specifically, the outputs of the first DO algorithm on two neighboring inputs may no longer be neighboring, and thus we cannot directly benefit from the DO guarantee of the second algorithm. In this work, we are the first to explore a theory of composition for differentially oblivious algorithms. We propose a refinement of the DO notion called $(\epsilon, \delta)$-neighbor-preserving-DO, or $(\epsilon, \delta)$-NPDO for short, and we prove that our new notion indeed provides nice compositional guarantees. In this way, the algorithm designer can easily track the privacy loss when composing multiple DO algorithms. We give several example applications to showcase the power and expressiveness of our new NPDO notion. One of these examples is a result of independent interest: we use the compositional framework to prove an optimal privacy amplification theorem for the differentially oblivious shuffle model. In other words, we show that for a class of distributed differentially private mechanisms in the shuffle-model, one can replace the perfectly secure shuffler with a DO shuffler, and nonetheless enjoy almost the same privacy amplification enabled by a shuffler.

Available format(s)
Publication info
A minor revision of an IACR publication in EUROCRYPT 2023
Differential PrivacyDifferential Obliviousness
Contact author(s)
mingxunz @ andrew cmu edu
runting @ cs cmu edu
hubert @ cs hku hk
shir @ cs cornell edu
2023-03-20: last of 3 revisions
2022-10-11: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial


      author = {Mingxun Zhou and Elaine Shi and T-H. Hubert Chan and Shir Maimon},
      title = {A Theory of Composition for Differential Obliviousness},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1357},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.