Differentially Private Histograms in the Shuffle Model from Fake Users
By Albert Cheu, Maxim Zhilyaev. 2021
42 citations recorded by the source corpus.
There has been much recent work in the shuffle model of differential privacy, particularly for approximate d-bin histograms. While these protocols achieve low error, the number of messages sent by each user—the message complexity—has so far scaled with d or the privacy parameters. The message complexity is an informative predictor of a shuffle protocol’s resource consumption. We present a protocol whose message complexity is two when there are sufficiently many users. The protocol essentially pairs each row in the dataset with a fake row and performs a simple randomization on all rows. We show that the error introduced by the protocol is small, using rigorous analysis as well as experiments on real-world data. We also prove that corrupt users have a relatively low impact on our protocol’s estimates.
Subfields: Artificial Intelligence
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
- Pasin Manurangsi
- Badih Ghazi
- Ravi Kumar
- Rasmus Pagh
- Amer Sinha
- Albert Cheu
- David P. Woodruff
- Alisa Chang
Citations in the corpus
- Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message (2021, background): “…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…”