# The Limits of Pan Privacy and Shuffle Privacy for Learning and Estimation

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Sep 2020.

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

- [Optimal Algorithms for Mean Estimation under Local Differential Privacy](https://mlsanity.com/paper/2205.02466/) (2022)
- [Stronger Privacy Amplification by Shuffling for R'enyi and Approximate Differential Privacy](https://mlsanity.com/paper/2208.04591/) (2022)
- [Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages](https://mlsanity.com/paper/2404.10201/) (2024)
- [System-Aware Unlearning Algorithms: Use Lesser, Forget Faster](https://mlsanity.com/paper/2506.06073/) (2025)
- [The Sample Complexity of Distribution-Free Parity Learning in the Robust Shuffle Model](https://mlsanity.com/paper/2103.15690/) (2021)
- [On the Curse of Dimensionality in Private Sparse Covariance Estimation and PCA](https://mlsanity.com/paper/2606.21951/) (2026)
- [Mitigating Leakage from Data Dependent Communications in Decentralized Computing using Differential Privacy](https://mlsanity.com/paper/2112.12411/) (2021)

## Abstract (arXiv)

There has been a recent wave of interest in intermediate trust models for differential privacy that eliminate the need for a fully trusted central data collector, but overcome the limitations of local differential privacy. This interest has led to the introduction of the shuffle model (Cheu et al., EUROCRYPT 2019; Erlingsson et al., SODA 2019) and revisiting the pan-private model (Dwork et al., ITCS 2010). The message of this line of work is that, for a variety of low-dimensional problems -- such as counts, means, and histograms -- these intermediate models offer nearly as much power as central differential privacy. However, there has been considerably less success using these models for high-dimensional learning and estimation problems. In this work, we show that, for a variety of high-dimensional learning and estimation problems, both the shuffle model and the pan-private model inherently incur an exponential price in sample complexity relative to the central model. For example, we show that, private agnostic learning of parity functions over d bits requires Omega(2d/2) samples in these models, and privately selecting the most common attribute from a set of d choices requires Omega(d1/2) samples, both of which are exponential separations from the central model. Our work gives the first non-trivial lower bounds for these problems for both the pan-private model and the general multi-message shuffle model.