Paper 2026/1218

High-Accuracy, Poisoning-Resilient Frequency Estimation in the Shuffle Model

Abstract

We study frequency estimation in the shuffle model of differential privacy under poisoning attacks, where corrupted users may deviate from the local randomizer to inject crafted in-domain messages. Existing shuffle-model protocols face a core tension: achieving low estimation error relies on flexible multi-message noise generation, which can amplify poisoning influence once messages are anonymized by shuffling. To address this tension, we propose a symmetric binomial-sum noise distribution (i.e., $\mathrm{Bin}(n/2,p) + \mathrm{Bin}(n/2,1-p)$), which preserves high accuracy while limiting the impact of crafted in-domain messages. We realize this distribution via preprocessing-guided noise generation, which routes a balanced collection of mode flags through the shuffler so that each user receives a randomly assigned mode flag that fixes their noise-sampling behavior prior to shuffling. For binary estimation, our protocol requires a single Bernoulli trial per user and at most $2$ messages per user ($1.5$ on average), while bounding the worst-case poisoning influence of a single corrupted user by $O(1/n)$. We extend the protocol to histograms, including large domains via hashing, and provide formal privacy, accuracy, and robustness guarantees. Experiments on real datasets show that our protocols remain resilient under poisoning and reduce MAE by up to nearly $2\times$ over the strongest baseline at comparable per-user communication on small-domain workloads, and stay on par with it on large domains.

Note: Full version of the paper accepted to the 35th USENIX Security Symposium, 2026.