Necessary Conditions in Multi-Server Differential Privacy
| Autor: | Cheu, Albert, Yan, Chao |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2023 |
| Předmět: |
FOS: Computer and information sciences
Security and privacy → Privacy protections Computer Science - Cryptography and Security Theory of computation → Sample complexity and generalization bounds Security and privacy → Information-theoretic techniques Mathematics of computing → Probabilistic algorithms Multi-server Differential Privacy Theory of computation → Distributed algorithms Parity Learning Theory of computation → Online algorithms Cryptography and Security (cs.CR) Security and privacy |
| DOI: | 10.4230/lipics.itcs.2023.36 |
| Popis: | We consider protocols where users communicate with multiple servers to perform a computation on the users' data. An adversary exerts semi-honest control over many of the parties but its view is differentially private with respect to honest users. Prior work described protocols that required multiple rounds of interaction or offered privacy against a computationally bounded adversary. Our work presents limitations of non-interactive protocols that offer privacy against unbounded adversaries. We show these protocols demand exponentially more samples for some learning and estimation tasks than centrally private counterparts. This means performing as well as the central model requires interactivity or computational differential privacy, or both. 22 pages |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|