Pufferfish Privacy Mechanisms for Correlated Data

on YouTube ↗43m

" summary

Proposes a concrete privacy framework for correlated data and two mechanisms: the Wasserstein mechanism uses the infinity-Wasserstein distance as an analog of global sensitivity; the Markov quilt mechanism finds local neighborhoods in Bayesian networks and adds noise proportional to neighborhood size with a correction from max‑influence. Implements the quilt algorithm in O(T^2) for Markov chains, proves composition, and shows empirical gains (100-step activity chain: L1 error 0.012 vs group‑DP 0.214); works when model class is restricted by stationary mass and eigengap.

AI-written summary · about

" chapters (30)

1. 0:00Intro
2. 1:04Sensitive Data
3. 1:31Correlated Data
4. 3:28Differential Privacy [DMNS06]
5. 3:48Differential Privacy: Attacker's View
6. 5:06Example 1: Activity Monitoring
7. 6:12Example 2: Spread of Flu in Network
8. 12:04Pufferfish Privacy [KMI2]
9. 17:41Pufferfish Generalizes DP [KMI2]
10. 19:02How to get Pufferfish privacy?
11. 19:43Intuition
12. 20:25Infinity Wasserstein Distance
13. 23:50Wasserstein Mechanism: Properties
14. 24:22Correlation Measure: Bayesian Networks
15. 24:59A Simple Example
16. 26:09Algorithm: Main Idea
17. 26:33Measuring "Independence"
18. 28:09Markov Blanket
19. 28:53Define: Markov Quilt
20. 29:56Recall: Algorithm
21. 30:15Why do we need Markov Quilts?
22. 31:13From Markov Quilts to Amount of Noise
23. 32:05The Markov Quilt Mechanism
24. 32:28Example: Activity Monitoring
25. 34:00Markov Quilt Mechanism for Activity Monitoring
26. 34:48Simulations - Task
27. 35:39Simulations - Results
28. 37:27Preliminary Experiments
29. 39:17Conclusion
30. 39:47Acknowledgements

" related talks

• 39mPufferfish Privacy Mechanisms for Correlated DataShuang Song · Privacy and the Science of Data Analysis 2019
• 29mVerifying Pufferfish Privacy in Hidden Markov ModelsBow-Yaw Wang, Depeng Liu, Lijun Zhang · VMCAI 2022
• 56mFormal Methods and Proofs of Privacy Properties, Part IIMarco Gaboardi · Data Privacy: Foundations and Applications Boot Camp
• 20mShare data without revealing personal informationGordon Haff · DevConf.CZ 2021
• 48mLocally Private Bayesian Inference for Count ModelsSteven Wu · Privacy and the Science of Data Analysis 2019
• 54mNode Privacy, High-dimensional Graph Summaries, and Block ModelsAdam M. Smith · Privacy and the Science of Data Analysis 2019
• 01h 11mStatistical Physics and Computation in High DimensionFlorent Krzakala, Lenka Zdeborova · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 46mFrom Health Data to Location Traces: Addressing Spatiotemporal Correlations in Differential PrivacyLi Xiong · Data Privacy: From Foundations to Applications (Simons Institute workshop, 2019)