Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead

By Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh. 2020

60 citations recorded by the source corpus.

Differential privacy (DP) is a formal notion for quantifying the privacy loss of algorithms. Algorithms in the central model of DP achieve high accuracy but make the strongest trust assumptions whereas those in the local DP model make the weakest trust assumptions but incur substantial accuracy loss. The shuffled DP model (Bittau et al., 2017; Erlingsson et al., 2019; Cheu et al., 2019) has recently emerged as a feasible middle ground between the central and local models, providing stronger trust assumptions than the former while promising higher accuracies than the latter. In this paper, we obtain practical communication-efficient algorithms in the shuffled DP model for two basic aggregation primitives used in machine learning: 1) binary summation, and 2) histograms over a moderate number of buckets. Our algorithms achieve accuracy that is arbitrarily close to that of central DP algorithms with an expected communication per user essentially matching what is needed without any privacy constraints! We demonstrate the practicality of our algorithms by experimentally comparing their performance to several widely-used protocols such as Randomized Response (Warner, 1965) and RAPPOR (Erlingsson et al., 2014).

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

Differentially Private Histograms in the Shuffle Model from Fake Users (2021, methodology): “[17] give a protocol where the message complexity shrinks as n increases.”
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…”
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.”