Private Aggregation from Fewer Anonymous Messages

Consider the setup where n parties are each given an element minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$x_i$documentxi in the finite field minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$\mathbb {F}_q$documentFq and the goal is to compute the sum minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$\sum _i x_i$document∑ixi in a secure fashion and with as little communication as possible. We study this problem in the anonymized model of Ishai et al. (FOCS 2006) where each party may broadcast anonymous messages on an insecure channel. We present a new analysis of the one-round “split and mix” protocol of Ishai et al. In order to achieve the same security parameter, our analysis reduces the required number of messages by a minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$\varTheta (\log n)$documentΘ(logn) multiplicative factor. We also prove lower bounds showing that the dependence of the number of messages on the domain size, the number of parties, and the security parameter is essentially tight. Using a reduction of Balle et al. (2019), our improved analysis of the protocol of Ishai et al. yields, in the same model, an minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$\left( \varepsilon , \delta \right)$documentε,δ-differentially private protocol for aggregation that, for any constant minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$\varepsilon > 0$documentε>0 and any minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$\delta = \frac{1}{\text {poly}(n)}$documentδ=1poly(n), incurs only a constant error and requires only a constant number of messages per party. Previously, such a protocol was known only for minimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs upgreek -69pt document$\varOmega (\log n)$documentΩ(logn) messages per party.