On Distributed Differential Privacy and Counting Distinct Elements
summary
Shows that distinct counting under constant-epsilon, delta = 1/poly(n) privacy is basically impossible in the local model: any local protocol needs error ≈ N / polylog N, and the single-message worst-case shuffle model inherits the same nearly-linear lower bound. Allowing O(1) messages in expectation (not worst-case) drops error to Θ(√N). Proofs use moment matching constructions plus the Poissonization trick to hide signals, and a reduction showing a K-message shuffle randomizer is ε + K ln N dominated, yielding dominated protocols lower bounds.
AI-written summary · about
chapters (17)
- 0:00Intro
- 0:15Today's Plan
- 1:05Differential Privacy: Definition
- 2:52Differential Privacy in the Distributed Setting
- 4:05Central Model vs (Non-interactive) Local Model
- 5:16Differential Privacy: Local Model
- 7:35Differential Privacy: Central vs Local vs Shuffle
- 8:23Shuffle Model: Definition
- 9:51The Count Distinct Problem Input: n users, each holds their own data
- 11:19Count Distinct in (Non-Interactive) Local Model
- 12:30Count Distinct in the Shuffle Model
- 13:45Other Lower Bounds in the Shuffle Model
- 17:18Lower Bounds for Count Distinct via Moment-Matching
- 19:46Hard Distribution: Signal/Noise Decomposition
- 22:42Hard Distribution: Poissonization Trick
- 24:16Lower Bounds in Shuffle Model via
- 26:19Conclusion and Open Problems
related talks
26mCounting Distinct Elements in the Message Passing Model
42mThe Privacy Blanket of the Shuffle Model
01h 00mDifferential Privacy: Fundamentals to Forefront I
58mLarge-Scale Private Learning, Part III
37mUser-level and federated local differential privacy
26mLocally Private Histograms in All Privacy Regimes
26mAlgorithms with More Granular Differential Privacy Guarantees
15mNecessary Conditions in Multi-Server Differential Privacy