Welcome to the resource topic for 2012/373
Title:
Optimal Lower Bound for Differentially Private Multi-Party Aggregation
Authors: T-H. Hubert Chan, Elaine Shi, 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.
ePrint: https://eprint.iacr.org/2012/373
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .