Optimal Lower Bound for Differentially Private Multi-Party Aggregation

Dwork et al. [DMNS06] proposed (information theoretical) differential privacy, which has become a de-facto standard privacy notion in private data analysis. In this paper, the authors investigate the setting of distributed private data analysis [BNO08], in which n parties each holds some private input, and they wish to jointly compute some statistic over all parties' inputs in a way that respects each party's privacy. In a seminal work by Beimel, Nissim, and Omri [BNO08], they demonstrate a lower bound result for distributed private data analysis. Specifically, they consider the distributed summation problem, namely, computing the sum of all parties' inputs. They prove that any differentially-private multi-party protocol with a small number of rounds and small number of messages must have large error.