Privacy amplification by shuffling

We describe a new and general privacy amplification technique based on shuffling the dataset before applying differentially private algorithms to disjoint subsets of the data. As a main corollary we show that any permutation-invariant algorithm satisfying $\epsilon$-local differential privacy (LDP) will satisfy $(O(\epsilon \sqrt{\log(1/\delta)/n}), \delta)$-central differential privacy. By this, we explain how the high noise and $\sqrt{n}$ overhead of LDP protocols is a consequence of them being significantly more private in the central model. As practical corollaries, our results imply formal privacy guarantees for the Encode-Shuffle-Analyze architecture of Bittau et al. (2017) and suggest that several LDP-based industrial deployments may have much lower privacy cost than their advertised $\epsilon$ would indicate.

Joint work with Úlfar Erlingsson, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, Abhradeep Thakurta