Separating Local & Shuffled Differential Privacy via Histograms
This work addresses the challenge of balancing privacy and accuracy in data analysis for researchers and practitioners, offering a novel separation between privacy models that could influence protocol design.
The authors tackled the problem of estimating histograms with differential privacy by introducing a protocol in the shuffled model that achieves error independent of domain size, demonstrating an arbitrarily large gap in sample complexity between shuffled and local models, while showing equivalence under pure differential privacy and single-message randomizers.
Recent work in differential privacy has highlighted the shuffled model as a promising avenue to compute accurate statistics while keeping raw data in users' hands. We present a protocol in this model that estimates histograms with error independent of the domain size. This implies an arbitrarily large gap in sample complexity between the shuffled and local models. On the other hand, the models are equivalent when we impose the constraints of pure differential privacy and single-message randomizers.