Abstract
Differential Privacy (DP) provides a rigorous framework for quantifying privacy loss, but standard composition theorems typically assume mechanisms are queried sequentially. This paper addresses the more complex scenario of concurrent composition, where an adversary interacts with multiple mechanisms simultaneously, interleaving queries adaptively. By leveraging the $f$-Differential Privacy ($f$-DP) framework, the authors prove that concurrent interaction is no more dangerous than sequential interaction. They establish a Simulation Theorem showing that any interactive $f$-DP mechanism can be viewed as post-processing of a non-interactive one, thereby extending all standard DP composition results to the concurrent setting.
The Challenge of Concurrent Interaction
In practical data science, analysts often interact with multiple privacy-preserving systems at once. An adversary might use the output of one mechanism to inform a query to another, then return to the first with a refined request. This "interleaving" of queries creates potential for sophisticated timing or correlation attacks.
Until this work, it was unclear if such concurrent interaction allowed for greater privacy leakage than standard sequential composition, particularly for widely used variants like $(\epsilon, \delta)$-DP and Rényi DP. While "pure" DP ($\delta=0$) was previously understood, the gap for approximate DP remained a significant theoretical hurdle.
Methodology: The Power of $f$-DP
The authors resolve this by employing $f$-Differential Privacy ($f$-DP), a functional approach to privacy that characterizes the trade-off between type I and type II errors in hypothesis testing. This framework is more flexible than the traditional $(\epsilon, \delta)$ parameters and allows for cleaner mathematical manipulation.
The central result is a Simulation Theorem, which posits that any interactive $f$-DP mechanism can be perfectly simulated by an interactive post-processing of a non-interactive $f$-DP mechanism. To prove this, the authors developed two technical pillars:
- A Coupling Property: A method to link random variables while preserving their privacy trade-off functions.
- A Chain Rule for $f$-DP: A way to decompose the privacy loss of joint distributions, analogous to the chain rule for information theory.
By applying these tools, the authors demonstrate that the adversary's ability to interleave queries is effectively an illusion; it does not grant them any more information than if they had interacted with the systems one by one.
Key Insights
- Interactivity as Post-Processing: The most significant insight is that interactivity does not inherently increase privacy risk. If a mechanism satisfies $f$-DP, its interactive behavior can be treated as post-processing of a non-interactive output. Since DP is immune to post-processing, the privacy guarantee remains intact.
- Mathematical Elegance of $f$-DP: The authors highlight that $(\epsilon, \delta)$-DP lacks a clean "chain rule," making these proofs difficult. The $f$-DP framework provides the necessary mathematical structure to close these theoretical gaps.
- Simplifying Rényi DP: The paper also simplifies the proof for concurrent composition of Rényi DP—a variant crucial for deep learning (e.g., DP-SGD)—by characterizing the adversary's optimal strategy.
Results and Implications
The paper proves that all known composition theorems for non-interactive DP (such as the Advanced Composition Theorem or the Moments Accountant) automatically extend to the concurrent interactive setting.
Specifically, the authors establish that concurrent composition for $(\epsilon, \delta)$-DP and $f$-DP follows the exact same rules as sequential composition. There is no "interleaving penalty." This result provides a theoretical "green light" for engineers to build complex, multi-user interactive DP systems without fear of hidden privacy vulnerabilities arising from concurrent access.
Limitations and Future Directions
While the paper provides a comprehensive solution for most practical cases, it assumes "finite communication"—a bounded number of messages. Extending these results to infinite-round protocols would require further topological exploration. Additionally, while the bounds are proven to exist, the computational complexity of calculating exact $f$-DP trade-offs for highly complex compositions remains an area for future research in privacy accounting.
Summary updated