Concurrent Composition of Differential Privacy

Salil P. Vadhan, Tianhao Wang

Abstract

We initiate a study of the composition properties of interactive differentially private mechanisms. An interactive differentially private mechanism is an algorithm that allows an analyst to adaptively ask queries about a sensitive dataset, with the property that an adversarial analyst's view of the interaction is approximately the same regardless of whether or not any individual's data is in the dataset. Previous studies of composition of differential privacy have focused on non-interactive algorithms, but interactive mechanisms are needed to capture many of the intended applications of differential privacy and a number of the important differentially private primitives. We focus on concurrent composition, where an adversary can arbitrarily interleave its queries to several differentially private mechanisms. We prove that when the interactive mechanisms being composed are pure differentially private, their concurrent composition achieves privacy parameters that match the optimal composition theorem for non-interactive differential privacy. We also prove a composition theorem for interactive mechanisms that satisfy approximate differential privacy, though the current bound remains weaker than the non-interactive counterpart.

Introduction

Differential Privacy (DP) has become the gold standard for protecting individual data in statistical analysis. A central feature of DP is its "composition" property, which allows researchers to reason about the total privacy loss when multiple analyses are performed on the same dataset. Traditionally, composition theorems have focused on non-interactive algorithms—where the analyst receives a single output—or sequential interactive algorithms—where the analyst finishes one interaction before starting the next.

However, real-world deployments often involve concurrent interactions. An adversary might engage with multiple interactive DP systems simultaneously, interleaving queries across different sessions to exploit potential correlations. This paper addresses whether this concurrent interleaving provides the adversary with any advantage over sequential querying.

Defining Interactive Mechanisms and Concurrency

The authors formalize an Interactive DP Mechanism as a two-party protocol between a curator (holding the dataset) and an analyst. In a concurrent setting, an adversary interacts with $k$ such mechanisms. Unlike sequential composition, where the adversary must complete interaction $i$ before starting $i+1$, concurrent composition allows the adversary to adaptively choose which mechanism to query at any given step based on all previous responses.

Theoretical Framework

The research employs three primary methodologies to analyze these interactions:

  1. The Hybrid Argument: Used to establish a "Basic Composition Theorem," this cryptographic technique tracks the degradation of privacy parameters $(\epsilon, \delta)$ as the number of mechanisms $k$ increases.
  2. The Simulation Theorem: For "pure" DP ($\delta=0$), the authors demonstrate that any interactive mechanism can be "simulated" by a non-interactive one. Specifically, they show that the interaction is equivalent to a version of Randomized Response. This reduction is powerful because it allows interactive mechanisms to inherit the tightest known composition bounds from the non-interactive literature.
  3. Linear Programming (LP) Analysis: To investigate approximate DP ($\delta > 0$), the authors used LP solvers to analyze over 10,000 synthetic parameter vectors representing 2-round interactive protocols. This empirical approach sought to determine if a non-interactive simulation exists for approximate DP mechanisms.

Key Results

Pure Differential Privacy

The most significant finding is that for pure DP, concurrency does not increase privacy risk. Corollary 1.11 confirms that the "Optimal Composition Theorem"—the tightest bound available for non-interactive DP—applies directly to concurrent interactive DP. This means that for systems using pure DP, developers do not need to worry about analysts interleaving their queries across different sessions.

Approximate Differential Privacy

The results for approximate DP ($\delta > 0$) are more nuanced. Theorem 1.8 provides a basic composition bound, but it reveals a gap: the $\delta$ parameter grows by a factor of approximately $e^{k\epsilon}$. This bound is weaker than the standard composition theorem for non-interactive DP. While the authors suspect this gap is an artifact of the proof technique rather than a fundamental vulnerability, it represents a significant theoretical challenge.

Experimental Verification

The LP trials provided strong evidence for the "Simulation Conjecture." For every 2-round protocol tested, the authors found a non-interactive simulation. This suggests that the optimal composition bounds might eventually be proven for approximate DP as well, provided the right mathematical framework is developed.

Limitations and Future Directions

While this work lays the foundation for understanding concurrent composition, several questions remain:

  • Closing the Approximate DP Gap: Improving the $(\epsilon, \delta)$ bounds to match the non-interactive case is a primary goal for future research.
  • Message Complexity: The experimental results focused on 1-bit messages. Extending these findings to continuous real-valued outputs (common in the Gaussian mechanism) is necessary for practical applications.
  • Alternative DP Definitions: Future studies should investigate whether concurrent composition properties hold for other variants like Rényi Differential Privacy (RDP) or Zero-Concentrated Differential Privacy (zCDP), which are frequently used in modern machine learning.

Conclusion

This study provides the first systematic treatment of concurrent composition in DP. By proving that pure DP is robust against interleaved queries, the authors provide critical safety guarantees for interactive systems. Although approximate DP requires further investigation to close the current theoretical gap, the evidence suggests that DP remains a robust framework even in complex, concurrent environments.

Summary updated

Abstract

We initiate a study of the composition properties of interactive differentially private mechanisms. An interactive differentially private mechanism is an algorithm that allows an analyst to adaptively ask queries about a sensitive dataset, with the property that an adversarial analyst's view of the interaction is approximately the same regardless of whether or not any individual's data is in the dataset. Previous studies of composition of differential privacy have focused on non-interactive algorithms, but interactive mechanisms are needed to capture many of the intended applications of differential privacy and a number of the important differentially private primitives. We focus on concurrent composition, where an adversary can arbitrarily interleave its queries to several differentially private mechanisms, which may be feasible when differentially private query systems are deployed in practice. We prove that when the interactive mechanisms being composed are pure differentially private, their concurrent composition achieves privacy parameters (with respect to pure or approximate differential privacy) that match the (optimal) composition theorem for noninteractive differential privacy. We also prove a composition theorem for interactive mechanisms that satisfy approximate differential privacy. That bound is weaker than even the basic (suboptimal) composition theorem for noninteractive differential privacy, and we leave closing the gap as a direction for future research, along with understanding concurrent composition for other variants of differential privacy.
BibTeX
@inproceedings{vadhan2021concurrent,
  author = {Salil P. Vadhan and Tianhao Wang},
  title = {{Concurrent Composition of Differential Privacy}},
  booktitle = {TCC},
  year = {2021},
  url = {https://openreview.net/forum?id=ijxGMLoodF7},
}
Figure