Pure Differentially Private Summation from Anonymous Messages

The shuffled (aka anonymous) model has recently generated significant interest as a candidate distributed privacy framework with trust assumptions better than the central model but with achievable errors smaller than the local model. We study pure differentially private (DP) protocols in the shuffled model for summation, a basic and widely used primitive: - For binary summation where each of n users holds a bit as an input, we give a pure ε-DP protocol for estimating the number of ones held by the users up to an error of Oε(1), and each user sends Oε(log n) messages each of 1 bit. This is the first pure protocol in the shuffled model with error o(√n) for constant ε. Using this protocol, we give a pure ε-DP protocol that performs summation of real numbers in [0, 1] up to an error of Oε(1), and where each user sends Oε(log3 n) messages each of O(loglog n) bits. - In contrast, we show that for any pure ε-DP protocol for binary summation in the shuffled model having absolute error n0.5-Omega(1), the per user communication has to be at least Omegaε(√log n) bits. This implies the first separation between the (bounded-communication) multi-message shuffled model and the central model, and the first separation between pure and approximate DP protocols in the shuffled model. To prove our lower bound, we consider (a generalization of) the following question: given γ in (0, 1), what is the smallest m for which there are two random variables X0, X1 supported on 0, dots ,m such that (i) the total variation distance between X0 and X1 is at least 1-γ, and (ii) the moment generating functions of X0 and X1 are within a constant factor of each other everywhere? We show that the answer is m = Theta(√log(1/γ)).