Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2023.36
URN: urn:nbn:de:0030-drops-175395
URL: https://drops.dagstuhl.de/opus/volltexte/2023/17539/
Cheu, Albert ; Yan, Chao
Necessary Conditions in Multi-Server Differential Privacy
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{cheu_et_al:LIPIcs.ITCS.2023.36,
author = {Cheu, Albert and Yan, Chao},
title = {{Necessary Conditions in Multi-Server Differential Privacy}},
booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
pages = {36:1--36:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-263-1},
ISSN = {1868-8969},
year = {2023},
volume = {251},
editor = {Tauman Kalai, Yael},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17539},
URN = {urn:nbn:de:0030-drops-175395},
doi = {10.4230/LIPIcs.ITCS.2023.36},
annote = {Keywords: Differential Privacy, Parity Learning, Multi-server}
}
| Keywords: | Differential Privacy, Parity Learning, Multi-server | |
| Seminar: | 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) | |
| Issue date: | 2023 | |
| Date of publication: | 01.02.2023 |
