Private Aggregation from Fewer Anonymous Messages

By Badih Ghazi, Pasin Manurangsi, Rasmus Pagh, Ameya Velingker. 2019

57 citations recorded by the source corpus.

Consider the setup where n parties are each given an element \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x_i$$\end{document}xi in the finite field \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {F}_q$$\end{document}Fq and the goal is to compute the sum \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sum _i x_i$$\end{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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varTheta (\log n)$$\end{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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\left( \varepsilon , \delta \right) $$\end{document}ε,δ-differentially private protocol for aggregation that, for any constant \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varepsilon > 0$$\end{document}ε>0 and any \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta = \frac{1}{\text {poly}(n)}$$\end{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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varOmega (\log n)$$\end{document}Ω(logn) messages per party.

Subfields: Artificial Intelligence, Federated & Distributed Learning, 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 Federated & Distributed Learning

In Privacy & Security

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “This can enable differentially private protocols with far smaller error than what is possible in the local model, while relying on weaker trust assumptions than in the central model [105, 157, 43, 179, 178].”
The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation (2021, methodology): “For more information on the shuffled model of DP, we refer the reader to Ghazi, Kumar, Manurangsi, and Pagh [GKMP20], Ghazi, Golowich, Kumar, Pagh, and Velingker [GGKPV21], Ghazi, Manurangsi, Pagh, and Velingker [GMPV20], Ghazi, Golowich, Kumar, Manurangsi, Pagh, and Velingker [GGKMPV20], Ishai, Kus”
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.”
Pure Differentially Private Summation from Anonymous Messages (2020, methodology): “…shuﬄed model (denoted DP ≥ 1 shuﬄed ), where a user can send more than one message, the state-of-the-art approximate protocol was recently obtained in [GMPV19, BBGN19b] and it incurs error at most O (1 /(cid:15) ) with every user sending O (1 + log(1 /δ ) log n ) messages of O (log n ) bits each.”
Scalable and Differentially Private Distributed Aggregation in the Shuffled Model (2019, background): “We point out that following the appearance of this work, tighter quantitative bounds for the secure aggregation problem that was studied in [12] were independently obtained in [10, 2].”
The Power of the Hybrid Model for Mean Estimation (2018, background): “However, DP mean estimation of distributions under both the TCM and LM has been studied since the models’ introductions [17, 21, 56], and continues to be actively studied to this day [2, 15, 18, 20, 22, 28, 29, 32, 37, 39–42].”
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.”
Improving utility and security of the shuffler-based differential privacy (2019, background): “Besides estimating histograms, the problem of estimating the sum of numerical values are also extensively investigated [34, 10].”
On the Round Complexity of the Shuffle Model (2020, background): “Already in this limited communication model there are fundamental statistical tasks for which differentially private shuffle model protocols exist with error comparable to that achievable in the (centralized) curator model of differential privacy [14, 5, 21, 4, 22, 6, 2, 23].”
Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message (2021, methodology): “…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 private mean estimation…”