On the Power of Multiple Anonymous Messages

By Badih Ghazi, Noah Golowich, Ravi Kumar, Rasmus Pagh, Ameya Velingker. 2019

112 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Privacy & Security, Information Theory

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

In Information Theory

Citations in the corpus

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”
On Distributed Differential Privacy and Counting Distinct Elements (2020, background): “…{ 0 , 1 } D → R , its Fourier transform is given by the we deﬁne the level-k Fourier weight as For convenience, for s ∈ { 0 , 1 } D , we will also write ˆ f ( s ) to denote f ( χ s ), where χ s is the set { i One key technical lemma is the Level-1 Inequality from [37], which was also used in [27].”
Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead (2020, background): “Furthermore, the recent histogram protocols of Ghazi et al. (2019a); Erlingsson et al. (2020), are also not applicable since they all incur an MSE of Ω(log n).”
Pure Differentially Private Summation from Anonymous Messages (2020, methodology): “We do so by invoking a result from the literature [CSS12, GGK + 19] showing that for any binary summation protocol that incurs an absolute error of α , the total variation distance between X 0 and X 1 must be at least 1 − Θ( α/ √ n ) (see Theorem 23 for more details).”
Private Aggregation from Fewer Anonymous Messages (2019, methodology): “The shuffled model is based on the Encode-Shuffle-Analyze architecture of [6] and was first analytically studied by [8,12] and further studied in recent work [4,13].”
The Power of the Hybrid Model for Mean Estimation (2018, background): “Several works have since improved the original analyses and expanded the shuffle model to achieve even greater improvements in the users’ DP guarantee [6, 7, 30–33].”
Separating Local & Shuffled Differential Privacy via Histograms (2019, methodology): “To simplify the presentation, we assume constant success probability, ε < 1, δ < 1 / log d for results from [13], and e − O ( nε 2 ) ≤ δ < 1 /n for our result.”
Connecting Robust Shuffle Privacy and Pan-Privacy (2020, methodology): “A generalization of Lemma 2.4 by Ghazi, Golowich, Kumar, Pagh, and Velingker [22] implies that setting p ≈ log(1 /δ ) ε 2 n guarantees ( ε, δ )-shuﬄe privacy, so the analyzer may recover estimates with error ≈ √ log(1 /δ ) ε .”
Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message (2021, methodology): “9 For the exact statement we use here, please refer to Theorem 13 of Ghazi et al. (2021b), which contains a correction of calculation errors in Theorem 13 of Ghazi et al. (2020b).”
Improving utility and security of the shuffler-based differential privacy (2019, background): “Parallel to our work, [8, 33] propose mechanisms to improve utility in this model.”
On the Round Complexity of the Shuffle Model (2020, methodology): “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 [15, 5, 22, 4, 23, 6, 2, 24].”
The limits of pan privacy and shuffle privacy for learning and estimation (2020, methodology): “[31], who obtained stronger bounds for single-message protocols.”
Locally Private k-Means in One Round (2021, methodology): “…shuﬄe DP model includes work on aggregation (Balle et al., 2019; Ghazi et al., 2020d; Balle et al., 2020; Ghazi et al., 2021b), histograms and heavy hitters (Ghazi et al., 2021a; Balcer and Cheu, 2020; Ghazi et al., 2020a,c), and counting distinct elements (Balcer et al., 2021; Chen et al., 2021).”