License: Creative Commons Attribution 4.0 International 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17539/
Go to the corresponding LIPIcs Volume Portal

Cheu, Albert ; Yan, Chao

Necessary Conditions in Multi-Server Differential Privacy

pdf-format:
LIPIcs-ITCS-2023-36.pdf (1 MB)

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
Collection: 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Issue Date: 2023
Date of publication: 01.02.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI