![[2601.19154] Analysis of Shuffling Beyond Pure Local Differential Privacy](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2601.19154] Analysis of Shuffling Beyond Pure Local Differential Privacy
Summary
This paper analyzes the effectiveness of shuffling in enhancing privacy beyond pure local differential privacy, introducing the concept of a shuffle index as a measure of efficiency.
Why It Matters
Understanding the limitations of traditional privacy measures is crucial as data privacy concerns grow. This research offers new insights into how shuffling can improve privacy guarantees in distributed data analysis, which is increasingly relevant in machine learning and data science applications.
Key Takeaways
- Shuffling can amplify privacy beyond pure local differential privacy parameters.
- The paper introduces the shuffle index as a new metric for evaluating shuffling efficiency.
- Asymptotic analysis reveals that blanket divergence is influenced by a single scalar parameter.
- The research provides a practical algorithm for computing blanket divergence with controlled error.
- Conditions for local randomizers that ensure tight privacy guarantees are established.
Computer Science > Data Structures and Algorithms arXiv:2601.19154 (cs) [Submitted on 27 Jan 2026 (v1), last revised 24 Feb 2026 (this version, v3)] Title:Analysis of Shuffling Beyond Pure Local Differential Privacy Authors:Shun Takagi, Seng Pei Liew View a PDF of the paper titled Analysis of Shuffling Beyond Pure Local Differential Privacy, by Shun Takagi and 1 other authors View PDF HTML (experimental) Abstract:Shuffling is a powerful way to amplify privacy of a local randomizer in private distributed data analysis. Most existing analyses of how shuffling amplifies privacy are based on the pure local differential privacy (DP) parameter $\varepsilon_0$. This paper raises the question of whether $\varepsilon_0$ adequately captures the privacy amplification. For example, since the Gaussian mechanism does not satisfy pure local DP for any finite $\varepsilon_0$, does it follow that shuffling yields weak amplification? To solve this problem, we revisit the privacy blanket bound of Balle et al. (the blanket divergence) and develop a direct asymptotic analysis that bypasses $\varepsilon_0$. Our key finding is that, asymptotically, the blanket divergence depends on the local mechanism only through a single scalar parameter $\chi$ and that this dependence is monotonic. Therefore, this parameter serves as a proxy for shuffling efficiency, which we call the shuffle index. By applying this analysis to both upper and lower bounds of the shuffled mechanism's privacy profile, we obtain...
