2 Search Results for "Cheu, Albert"

Document
DOI: 10.4230/LIPIcs.ITCS.2023.36
Necessary Conditions in Multi-Server Differential Privacy

Authors: Albert Cheu and Chao Yan

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

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.
Cite as

Albert Cheu and Chao Yan. Necessary Conditions in Multi-Server Differential Privacy. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 36:1-36:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.36},
  URN =		{urn:nbn:de:0030-drops-175395},
  doi =		{10.4230/LIPIcs.ITCS.2023.36},
  annote =	{Keywords: Differential Privacy, Parity Learning, Multi-server}
}
Document
DOI: 10.4230/LIPIcs.ITC.2020.1
Separating Local & Shuffled Differential Privacy via Histograms

Authors: Victor Balcer and Albert Cheu

Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)

Abstract
Recent work in differential privacy has highlighted the shuffled model as a promising avenue to compute accurate statistics while keeping raw data in users' hands. We present a protocol in this model that estimates histograms with error independent of the domain size. This implies an arbitrarily large gap in sample complexity between the shuffled and local models. On the other hand, we show that the models are equivalent when we impose the constraints of pure differential privacy and single-message randomizers.
Cite as

Victor Balcer and Albert Cheu. Separating Local & Shuffled Differential Privacy via Histograms. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 1:1-1:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{balcer_et_al:LIPIcs.ITC.2020.1,
  author =	{Balcer, Victor and Cheu, Albert},
  title =	{{Separating Local \& Shuffled Differential Privacy via Histograms}},
  booktitle =	{1st Conference on Information-Theoretic Cryptography (ITC 2020)},
  pages =	{1:1--1:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-151-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{163},
  editor =	{Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.1},
  URN =		{urn:nbn:de:0030-drops-121068},
  doi =		{10.4230/LIPIcs.ITC.2020.1},
  annote =	{Keywords: Differential Privacy, Distributed Protocols, Histograms}
}
  • Refine by Author
  • 2 Cheu, Albert
  • 1 Balcer, Victor
  • 1 Yan, Chao

  • Refine by Classification
  • 1 Mathematics of computing → Probabilistic algorithms
  • 1 Security and privacy
  • 1 Security and privacy → Information-theoretic techniques
  • 1 Security and privacy → Privacy protections
  • 1 Security and privacy → Privacy-preserving protocols
  • Show More...

  • Refine by Keyword
  • 2 Differential Privacy
  • 1 Distributed Protocols
  • 1 Histograms
  • 1 Multi-server
  • 1 Parity Learning

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2020
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact