International Association
for Cryptologic Research

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$.