Pure Differentially Private Summation from Anonymous Messages

By Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, Ameya Velingker. 2020

51 citations recorded by the source corpus.

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. - In contrast, we show that for any pure $\epsilon$-DP protocol for binary summation in the shuffled model having absolute error $n^{0.5-\Omega(1)}$, the per user communication has to be at least $\Omega_{\epsilon}(\sqrt{\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 $\gamma$ in $(0, 1)$, what is the smallest m for which there are two random variables $X^0, X^1$ supported on $\{0, \dots ,m\}$ such that (i) the total variation distance between $X^0$ and $X^1$ is at least $1-\gamma$, and (ii) the moment generating functions of $X^0$ and $X^1$ are within a constant factor of each other everywhere? We show that the answer is $m = \Theta(\sqrt{\log(1/\gamma)})$.

Subfields: Artificial Intelligence, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Privacy & Security

Citations in the corpus

Privacy Amplification by Decentralization (2020, background): “…2011; Bonawitz et al., 2017; Chan et al., 2012b; Jayaraman et al., 2018; Bell et al., 2020; Sabater et al., 2020) or to securely shuﬄe the set of user messages so as to hide their source (Cheu et al., 2019; Erlingsson et al., 2019; Balle et al., 2019b,a; Ghazi et al., 2020; Feldman et al., 2020).”
Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead (2020, methodology): “…encryption overhead increases with the number of messages, and hence our almost single-message protocols would be even more appealing compared to other multi-message procedures as in Ghazi et al. (2020b); Balle et al. (2020); Ghazi et al. (2019a) when the encryption costs are taken into account.”
Private Aggregation from Fewer Anonymous Messages (2019, background): “A subsequent work [14] obtained an (ε, 0)-differentially private aggregation protocol with error Oε(1) and where each user sends Oε(log(3) n) messages each consisting of O(log log n) bits (see Fig.”
Separating Local & Shuffled Differential Privacy via Histograms (2019, background): “Another class of lower bound comes from a lemma in [12]: when a shuffled protocol obeys εdifferential privacy and bounded communication complexity, the set of messages output by each user is insensitive to their personal data.”
Connecting Robust Shuffle Privacy and Pan-Privacy (2020, methodology): “One exception is the summation lower bound of Ghazi et al. [24], but it holds only if each user is limited to O ( poly log( n )) communication.”
Locally Private k-Means in One Round (2021, methodology): “Furthermore, we remark that the above guarantees essentially match those of the central DP algorithm of Ghazi et al. (2020b), while our algorithm works even in the more restrictive shuﬄe DP model.”
Distributed Differentially Private Averaging with Improved Utility and Robustness to Malicious Parties (2020, background): “Recently, the shufﬂe model of privacy [25, 34, 6, 44, 5, 41], where inputs are passed to a secure shufﬂer that obfuscates the source of the messages, has been studied theoretically as an intermediate point between the local and trusted curator models.”
On the Power of Multiple Anonymous Messages (2019, unknown): “After the initial release of this paper, Ghazi et al. [58] proved a similar anti-concentration lemma to establish a lower bound on private summation for protocols with short messages.”
Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message (2021, methodology): “…(Balle et al., 2019; Ghazi et al., 2020c; Balle et al., 2020), analytics tasks including computing histograms and heavy hitters (Ghazi et al., 2021a; Balcer & Cheu, 2020; Ghazi et al., 2020a;b; Cheu & Zhilyaev, 2021), counting distinct elements (Balcer et al., 2021; Chen et al., 2021) and…”