View article

Recent work of Erlingsson, Feldman, Mironov, Raghunathan, Talwar, and Thakurta [1] demonstrates that random shuffling amplifies differential privacy guarantees of locally randomized data. Such amplification implies substan-tially stronger privacy guarantees for systems in which data is contributed anonymously [2] and has lead to significant interest in the shuffle model of privacy [3], [1]. We give a characterization of the privacy guarantee of the random shuffling of data records input to epsilon-differentially private local randomizers that significantly im-proves over previous work and achieves the asymptotically optimal dependence in epsilon. Our result is based on a new approach that is simpler than previous work and extends to approximate differential privacy with nearly the same guarantees. Importantly, our work also yields an algorithm for deriving tighter bounds on the resulting epsilon and delta as well as …