Paper 2023/842

Advanced Composition Theorems for Differential Obliviousness

Mingxun Zhou, Carnegie Mellon University
Mengshi Zhao, University of Hong Kong
T-H. Hubert Chan, University of Hong Kong
Elaine Shi, Carnegie Mellon University

Differential obliviousness (DO) is a privacy notion which mandates that the access patterns of a program satisfy differential privacy. Earlier works have shown that in numerous applications, differential obliviousness allows us to circumvent fundamental barriers pertaining to fully oblivious algorithms, resulting in asymptotical (and sometimes even polynomial) performance improvements. Although DO has been applied to various contexts, including the design of algorithms, data structures, and protocols, its compositional properties are not explored until the recent work of Zhou et al. (Eurocrypt'23). Specifically, Zhou et al. showed that the original DO notion is not composable. They then proposed a refinement of DO called neighbor-preserving differential obliviousness (NPDO), and proved a basic composition for NPDO. In Zhou et al.'s basic composition theorem for NPDO, the privacy loss is linear in $k$ for $k$-fold composition. In comparison, for standard differential privacy, we can enjoy roughly $\sqrt{k}$ loss for $k$-fold composition by applying the well-known advanced composition theorem. Therefore, a natural question left open by their work is whether we can also prove an analogous advanced composition for NPDO. In this paper, we answer this question affirmatively. As a key step in proving an advanced composition theorem for NPDO, we define a more operational notion called symmetric NPDO which we prove to be equivalent to NPDO. Using symmetric NPDO as a stepping stone, we also show how to generalize NPDO to more general notions of divergence, resulting in Rényi-NPDO, zero-concentrated NPDO, Gassian-NPDO, and $g$-NPDO notions. We also prove composition theorems for these generalized notions of NPDO.

Available format(s)
Publication info
Published elsewhere. Minor revision. ITCS 2024
Differential Obliviousness
Contact author(s)
mingxunz @ andrew cmu edu
zmsxsl @ connect hku hk
hubert @ cs hku hk
runting @ gmail com
2023-11-09: last of 4 revisions
2023-06-06: received
See all versions
Short URL
Creative Commons Attribution


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