Necessary Conditions in Multi-Server Differential Privacy
summary
Shows that the non-interactive multi-server differential privacy model cannot learn parity with polynomial samples against an unbounded adversary when up to half the servers are compromised, giving exponential sample lower bounds instead. Proves this by simulating any non-interactive multi-server protocol with an internally private online protocol via a reduction to a two-server simulation and a private rejection sampling construction, then transfers known information-theoretic lower bounds (parity, feature selection, simple hypothesis and uniformity tests). Limitation: only one-round non-interactive protocols.
AI-written summary · about
chapters (5)
- 0:00Introduction
- 1:04Differential Privacy
- 2:08Decentralizing Differential Privacy
- 8:03Simulation
- 13:32Limitations
related talks
58mLarge-Scale Private Learning, Part III
27mOn Distributed Differential Privacy and Counting Distinct Elements
01h 08mTutorial: Security
38mDemystifying Privacy Preserving Computing
28mPrivacy versus Robustness in Federated Learning: Limits and Algorithms
21mModular Verification of Differential Privacy in Probabilistic Higher-Order Separation(…)
01h 00mDifferential Privacy: Fundamentals to Forefront I
43mDifferential Privacy Meets Robust Statistics