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 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 -party protocol
computing the sum with sparse communication graph
must incur an additive error
of
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 , 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
differential
privacy notion, for reasonably small values of .
@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},
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.