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

Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review


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).
Original languageEnglish
Title of host publicationProceedings of the 37th International Conference on Machine Learning
PublisherML Research Press
Publication date2020
Publication statusPublished - 2020


  • Differential Privacy
  • Shuffled DP Model
  • Communication-efficient Algorithms
  • Binary Summation
  • Histograms
  • Machine Learning Aggregation
  • Privacy Loss Quantification
  • Central Model
  • Local Model
  • Randomized Response


Dive into the research topics of 'Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead'. Together they form a unique fingerprint.

Cite this