Composition Theorems for Interactive Differential Privacy
Nov 28, 2022
About
An interactive mechanism is an algorithm that stores a data set and answers adaptively chosen queries to it. The mechanism is called differentially private, if any adversary cannot distinguish whether a specific individual is in the data set by interacting with the mechanism. We study composition properties of differential privacy in concurrent compositions. In this setting, an adversary interacts with k interactive mechanisms in parallel and can interleave its queries to the mechanisms arbitrarily. Previously, Vadhan and Wang [TCC 2021] proved an optimal concurrent composition theorem for pure-differential privacy. We significantly generalize and extend their results. Namely, we prove optimal parallel composition properties for several major notions of differential privacy in the literature, including approximate DP, Renyi DP, and zero-concentrated DP. Our results demonstrate that the adversary gains no advantage by interleaving its queries to independently running mechanisms. Hence, interactivity is a feature that differential privacy grants us for free.An interactive mechanism is an algorithm that stores a data set and answers adaptively chosen queries to it. The mechanism is called differentially private, if any adversary cannot distinguish whether a specific individual is in the data set by interacting with the mechanism. We study composition properties of differential privacy in concurrent compositions. In this setting, an adversary interacts with k interactive mechanisms in parallel and can interleave its queries to the mechanisms arbitrar…
Organizer
NeurIPS 2022
Account · 954 followers
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Near-Optimal No-Regret Learning Dynamics for General Convex Games
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Towards Understanding the Condensation of Neural Networks at Initial Training
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
DARE: Disentanglement-Augmented Rationale Extraction
Watch later
Linan Yue, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
(De)Noise: Moderating the Inconsistency of Human Decisions
Watch later
Junaid Ali, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Data augmentation for efficient learning from parametric experts
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Cost-Sensitive Self-Training for Optimizing Non-Decomposable Metrics
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%