# Differentially Private Histograms in the Shuffle Model from Fake Users

arXiv: https://arxiv.org/abs/2104.02739 · HTML: https://mlsanity.com/paper/2104.02739/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Apr 2021.

## Built on by (most cited first, 4 of 4)

- [User-Level Private Learning via Correlated Sampling](https://mlsanity.com/paper/2110.11208/) (2021)
- [Group privacy for personalized federated learning](https://mlsanity.com/paper/2206.03396/) (2022)
- [On the Robustness of LDP Protocols for Numerical Attributes under Data Poisoning Attacks](https://mlsanity.com/paper/2403.19510/) (2024)
- [Learning from End User Data with Shuffled Differential Privacy over Kernel Densities](https://mlsanity.com/paper/2502.14087/) (2025)

## Abstract (arXiv)

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.