2026-08-03T14:48:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17539 2024-03-06T10:59:51Z ddc:004 open_access

Necessary Conditions in Multi-Server Differential Privacy Cheu, Albert Yan, Chao Differential Privacy Parity Learning Multi-server 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 prove that these protocols require exponentially more samples than centrally private counterparts to solve some learning, testing, and estimation tasks. This means sample-efficiency demands interactivity or computational differential privacy, or both. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Albert Cheu and Chao Yan 2023 Is Part Of LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2023.36 urn:nbn:de:0030-drops-175395 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.36 eng https://creativecommons.org/licenses/by/4.0/legalcode