Paper 2012/373

Optimal Lower Bound for Differentially Private Multi-Party Aggregation

T-H. Hubert Chan, Elaine Shi, and Dawn Song

Abstract

We consider distributed private data analysis, where $n$ parties each holding some sensitive data wish to compute some aggregate statistics over all parties' data. We prove a tight lower bound for the private distributed summation problem. Our lower bound is strictly stronger than the prior lower-bound result by Beimel, Nissim, and Omri published in CRYPTO 2008. In particular, we show that any $n$-party protocol computing the sum with sparse communication graph must incur an additive error of $\Omega(\sqrt{n})$ with constant probability, in order to defend against potential coalitions of compromised users. Furthermore, we show that in the client-server communication model, where all users communicate solely with an untrusted server, the additive error must be $\Omega(\sqrt{n})$, regardless of the number of messages or rounds. Both of our lower-bounds, for the general setting and the client-to-server communication model, are strictly stronger than those of Beimel, Nissim and Omri, since we remove the assumption on the number of rounds (and also the number of messages in the client-to-server communication model). Our lower bounds generalize to the $(\epsilon, \delta)$ differential privacy notion, for reasonably small values of $\delta$.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. European Symposium on Algorithms 2012
Contact author(s)
hubert @ cs cmu edu
History
2012-07-05: received
Short URL
https://ia.cr/2012/373
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/373,
      author = {T-H.  Hubert Chan and Elaine Shi and Dawn Song},
      title = {Optimal Lower Bound for Differentially Private Multi-Party Aggregation},
      howpublished = {Cryptology ePrint Archive, Paper 2012/373},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/373}},
      url = {https://eprint.iacr.org/2012/373}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.