Separating Local & Shuffled Differential Privacy via Histograms

By Victor Balcer, Albert Cheu. 2019

78 citations recorded by the source corpus.

Recent work in differential privacy has highlighted the shuffled model as a promising avenue to compute accurate statistics while keeping raw data in users' hands. We present a protocol in this model that estimates histograms with error independent of the domain size. This implies an arbitrarily large gap in sample complexity between the shuffled and local models. On the other hand, the models are equivalent when we impose the constraints of pure differential privacy and single-message randomizers.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering, 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 Electrical and Electronic Engineering

In Privacy & Security

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 et al. (2020b; 2021; 2020c;a); Ishai et al. (2006); Balle et al. (2019; 2020); Balcer & Cheu (2020); Balcer et al. (2021); Girgis et al. (2020).”
Privacy Amplification via Random Check-Ins (2020, background): “There is also a growing line of works on privacy amplification by shuffling [10, 19, 12, 4, 6, 22, 18] that focus on various ways in which protocols can be designed using trusted shuffling primitives.”
Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead (2020, background): “Recently, Balcer & Cheu (2020) obtained a protocol with error independent of B but logarithmic in n, albeit with a per-user communication of O(B) messages each consisting of O(logB) bits.”
The Power of the Hybrid Model for Mean Estimation (2018, background): “Conversely, the LM users may experience privacy amplification through the combination of their locally-added noise; however, this is solely due to intra-group interaction in the LM, and related topics are currently an active area of research on the LM [5, 6, 16, 19, 26, 33].”
Connecting Robust Shuffle Privacy and Pan-Privacy (2020, methodology): “Speciﬁcally, Balcer and Cheu [7] gave a shuﬄe private protocol for estimating histograms with error independent of the domain size.”
Differentially Private Histograms in the Shuffle Model from Fake Users (2021, methodology): “This flexibility is leveraged by the histogram protocol of Balcer & Cheu [2], where each user sends d + 1 messages and the maximum error is O( 1 ε2 log 1 δ ) for δ = O(1/n).”
Locally Private k-Means in One Round (2021, unknown): “…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).”
On the Round Complexity of the Shuffle Model (2020, methodology): “Independent and parallel to our work, Cheu and Ullman [15] presented exponential separations between the 1-round shuffle model and the (centralized) curator model of differential privacy.”
Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message (2021, unknown): “…(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 private…”
The limits of pan privacy and shuffle privacy for learning and estimation (2020, methodology): “KEYWORDS Differential Privacy, Pan-Privacy, Shuffle Model, Lower Bounds ACM Reference Format: Albert Cheu and Jonathan Ullman.”