Pure Differentially Private Summation from Anonymous Messages

Understand

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 $\epsilon$-DP protocol for estimating the number of ones held by the users up to an error of $O_\epsilon(1)$, and each user sends $O_\epsilon(\log n)$ messages each of 1 bit.
• This is the first pure protocol in the shuffled model with error $o(\sqrt{n})$ for constant $\epsilon$.
• Using this protocol, we give a pure $\epsilon$-DP protocol that performs summation of real numbers in $[0, 1]$ up to an error of $O_{\epsilon}(1)$, and where each user sends $O_{\epsilon}(\log^3 n)$ messages each of $O(\log\log n)$ bits.