Stronger Privacy Amplification by Shuffling for Rényi and Approximate Differential Privacy
This work provides stronger privacy protections for systems with anonymous data contributions, representing an incremental theoretical and numerical improvement over prior methods.
The paper tackles the problem of enhancing privacy guarantees in the shuffle model of differential privacy by improving privacy amplification through shuffling, achieving asymptotically optimal analysis for Rényi differential privacy and tighter numerical bounds across all parameters.
The shuffle model of differential privacy has gained significant interest as an intermediate trust model between the standard local and central models [EFMRTT19; CSUZZ19]. A key result in this model is that randomly shuffling locally randomized data amplifies differential privacy guarantees. Such amplification implies substantially stronger privacy guarantees for systems in which data is contributed anonymously [BEMMRLRKTS17]. In this work, we improve the state of the art privacy amplification by shuffling results both theoretically and numerically. Our first contribution is the first asymptotically optimal analysis of the Rényi differential privacy parameters for the shuffled outputs of LDP randomizers. Our second contribution is a new analysis of privacy amplification by shuffling. This analysis improves on the techniques of [FMT20] and leads to tighter numerical bounds in all parameter settings.